Convert array of positive numbers to sorted array

You are given an array of positive integers. Convert it to a sorted array with minimum cost.
Only valid operation are
1) Decrement -> cost = 1
2) Delete an element completely from the array -> cost = value of element
For example:
4,3,5,6, -> cost 1 (decrement 4)
10,3,11,12 -> cost 3  (delete 3)

Trying out DP
We can make the DP more efficient You don't need to scan the whole previous column when calculating costs of decrementing. Rather there are only two possibilities.


Remember C(n, m) is the cost of making a[1 .. n] into a non-decreasing sequence with the last element being no more than m. And we always draw m from the set V of values in a[].
So here is the new DP:

C(1, m) = max(a[1] - m, 0)  // first row only decrement is possible 
C(n, m) = min ( 
a[n] + C(n - 1, m),   // delete 
(a[n] <= m) ?  C(n - 1, a[n]) : C(n - 1, m) + a[n] - m // decrement 
) 

In case you don't follow, the "//delete" line is saying that we already know the cost of making everything up to element n-1 non-decreasing and no more than m. This, by recursive assumption, is just C(n-1,m). The additional cost of deleting a[n] is a[n].
The "//decrement" line is similar, but there are 2 cases. If a[n] is more than m, we must decrement it. The cost here consists of making everything up to n-1 non-decreasing and no more than m, i.e. C(n-1,m). Plus we have the cost of chopping a[n] down to m, which is a[n]-m.

In the other case, a[n] is m or less. So there's no need todecrement, but we must get the elements a[1..n-1] to be no more thana[n]. Again by recursive assumption this cost is C(n-1,a[n]).Here is an example. Suppose we have a = [5, 1, 1, 1, 3, 1]. Theleast cost here is obtained by decrementing the 5 to 1 (cost 4) and
deleting the final 1 (cost 1) for a total cost of 5.So let's try the algorithm. (You must view this with a fixed font.)
Table of C(n, m) values:
m = 1 3 5
n = 1 : 4 2 0
n = 2 : 4 3* 1*
n = 3 : 4 4 2*
n = 4 : 4 4 3*
n = 5 : 6m 4 4
n = 6 : 6 5* 5*
Here * means C resulted from decrementing and "m" means that a decrement was based on the value of m rather than a[n].We take the answer from C(6,5) = 5.Implementing this is a little tricky because m values are drawn from V. You could use a hash table for the m-axis. But it's more efficient to store V in an array and convert all the values of m in the DP into indices of V. Because all the indices lie in [ 1 .. |V| ], we can use  simple arrays rather than hash tables to representthe rows of the table C.
We only need 2 rows at a time, so O(|V|) storage does the job.For C, we also need to convert all the indices to origin 0. So here's the final O(n^2) code. I think this is a correct implementation. If anyone has an example that breaks it, I'd like to see.

Also see - http://www.careercup.com/question?id=3603906