help with optimal cut/paste algo

[amitc]

The problem states that given a set of numbers, find the minimum number of cut/paste operations required to get the numbers into a sorted sequence. The cut operation can involve one or more consecutive numbers.

For eg.
given the sequence
1)
...2 4 1 5 3 6
we cut 4 and paste it before 5 to get,
...1 2 4 5 3 6
then we cut 5 and paste it after 2,
...1 2 3 4 5 6


another example,
2)
12 6 7 2 3 4 9 10 11 1 5 8 13 14 15
12 6 7 9 10 11 1 2 3 4 5 8 13 14 15
12 9 10 11 1 2 3 4 5 6 7 8 13 14 15
12 1 2 3 4 5 6 7 8 9 10 11 13 14 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15


I tried implementing a greedy solution which would attempt to find a single element or group whose cut/paste operation into the correct place would result in a smaller set of non consecutive elements and larger groups. It seemed to work for the above cases and even gave the same output, however while testing with some random data some test cases were generating wrong results.

Is there a DP solution to this problem? Any hints will be appreciated...


Thanks,
amit