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 element
Any solution? convert here means you can get a different sequence, but it must be non decreasing.
A possible solution is with DP. C(n, m) = is the cost of getting n non decreasing elements with the constrain tha no element is greater than m. note that given the # cardinality of the set made up of the elements in #set(A), then 0 < m < #set(A)
C(1,m) = max(a[1] - m, 0) // because at first step you can only decrease of value m
C(n, m) = min ( // min: two options and want to find the min cost
a[n] + C(n - 1, m), // delete operation at step n for value m
// express the cost in function of step n-1 for value m// and sum the cost of the specific delete op as specified
// decrement
(a[n] <= m) ?
C(n - 1, a[n]) // there is no need to decrement but for having
// a non decreasing sequence we must have a value
// non larger than a[n] for a[1..n-1]. That is
// expressed inductively by C(n-1, a[n])
: C(n-1, m) + // decrement with cost m
a[n]- m // cost of decrementing a[n] to m with a[n] - m ops
)
Posts
