Hello everyone, I found this problem a while ago and I'm still stuck on it (there's no OJ to submit it as far as I know):
You are given a permutation of the integers from 1 to N. In this case, moving an element from i to j is defined as removing the element from position i, and inserting it at position j. For example, in this array:
[4,5,2,1,3], moving the element from 2 to 5 gives us the array
[4,2,1,3,5]. The cost of moving an element from i to j is defined as i + j (1-indexed).
What is the minimum total cost needed to sort the permutation?
[1,2,3,4,5] with total cost 5 + 2 = 7.
1 ≤ N ≤ 1000, however solutions with any reasonable complexity are welcome.