Problem: Given an array of positive integers, and you only have two operations : a) decrease an integer by
k with a cost of k; b) delete an integer with a cost of the value of that integer. Try to use these two operations to convert the array into a sorted array with minmum cost. For example, a[] = {5,4,7,3}, the optimal way is to decrease "5" by 1 and delete "3" with the total cost of 4 (1+3). The resulting sorted array is {4, 4, 7}.
Solution: Here I give a O(N^2) solution by using DP. The key data structure we need is dp[
i] which records
the minimum cost to covert a subarray a[0, i] into sorted array and the last element of the sorted array should be a[i]. For the example array a[] = {5,4,7,3}, dp[0] = 0, dp[1] = 1 (since we need to decrease "5" by 1), dp[2] = 1, dp[3] = 7. After we had filled up dp[], we need one more data structure: aggr[]. aggr[i] = a[0] + a[1] + ... + a[i]. Then the minmum cost to convert the whole array
cost_min = min{dp[i] + aggr[N-1] - aggr[i]}. Here "aggr[N-1] - aggr[i]" means the cost that we delete all the elements with a subscript larger than
i.
Then the key is to calculate dp[
i]. There are several observations here:
- if a[i] >= a[j] (j<i), we can construct a sorted array ended at a[i] by deleting a[j+1], a[j+2], ... , a[i-1] and then append a[i]. The cost of the resulting sorted array is dp[j] + the cost of deleting a[j+1], a[j+2], ... , a[i-1].
- if a[i] < a[j], to have a[i] as the last element, we need to decrease a[j] by a[j] - a[i]. Moreover, we may not stop at a[j] and we need to keep look backward until we found a a[m] such that a[m] <= a[i], then the cost of the resulting sorted array is dp[m+1] + ∑(a[k] - a[i]) where m<k<j.
- To compute dp[i], we need to look at all the j such that j<i, depending on a[j] and a[i], we need to calculate the cost based on step 1 or 2. Then the minmum cost we encounter is the value of dp[i].
The code is as follow:
int min_convert_cost(int a[], int n)
{
int dp[n];
int aggr[n];
aggr[0] = a[0];
for(int i=1; i<n; i++)
aggr[i] = aggr[i-1] + a[i];
dp[0] = 0;
for(int i=1; i<n; i++)
{
dp[i] = INT_MAX;
for(int j=i-1; j>=0; j--)
{
int cost_i = 0;
if(a[i] >= a[j])
{
cost_i = dp[j] + aggr[i-1] - aggr[j];
}
else
{
cost_i += aggr[i-1] - aggr[j];
while(a[j]>a[i] && j >=0)
{
cost_i += a[j]-a[i];
j--;
}
cost_i += dp[j+1];
}
if(cost_i < dp[i])
dp[i] = cost_i;
}
}
int min = INT_MAX;
for(int i=0; i<n; i++)
{
int cost_i = dp[i] + aggr[n-1] - aggr[i];
if(cost_i<min) min = cost_i;
}
return min;
}
