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? ↵
Example: ↵
`[1,3,4,5,2]`->→ `[1,2,3,4,5]` with total cost $5+2=7$. ↵
$1 \leq N \leq 1000$, however solutions with any reasonable complexity are welcome.
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? ↵
Example: ↵
`[1,3,4,5,2]`
$1 \leq N \leq 1000$, however solutions with any reasonable complexity are welcome.
