Given an array A of positive integers. Convert it to a sorted array with
minimum cost. The only valid operation are:
1) Decrement with cost = 1
2) Delete an element completely from the array with cost = value of elemen11
e******s 发帖数: 38
2
I think we can use DP.
Cost(1...i) = Cost(1...i-1) if(A[i-1] <= A[i])
min(Cost(1...i-1) + A[i], sum_{j= P(i) ...i-1}(A[j]-A[i]))
otherwise.
P(i) is the left most index with A[P(i)] > A[i].
