Adjust a positive array to be sorted with minimum cost

Problem: 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
For example, input array is [10, 3, 11, 12]. The sorted array with minimum cost will be [10, 11, 12]. Cost is 3.

This problem confused me for a long time, until Junmin gave out the answer. The explanation is copied form Junmin:
The idea is that the final sorted array will always end up with one of the original numbers appear in the array. then all of the larger numbers before this number will be decremented,  dp(i, j), i is the index of the original array a[], j is the index of the sorted array b[] of unique numbers in the array
dp(i, j) = min(dp(i-1, 0), dp(i-1, 2), … dp(i-1, j)) + cost_of_convert(a[i], b[j]).

Based on that, my code also output the final sorted array.

1. import java.util.ArrayList;
2. import java.util.Arrays;
3. import java.util.List;
4. import java.util.Set;
5. import java.util.TreeSet;
6. public class LowestCostToSort {
7.     public static void main(String[] args) {
8.         int[] num = { 1, 5, 2, 2 };
9.         System.out.println(“input array:\t” + Arrays.toString(num));
10.         int cost = getLowestCostToSort(num);
11.         System.out.println(“total cost:\t” + cost);
12.     }
13.     public static int getLowestCostToSort(int[] num) {
14.         Set<Integer> uniqueSet = new TreeSet<Integer>();
15.         for (int i : num) {
16.             uniqueSet.add(i);
17.         }
18.         Integer[] uniqueNum = (Integer[]) uniqueSet
19.                 .toArray(new Integer[uniqueSet.size()]);
20.         CostTrack[][] dp = new CostTrack[num.length][uniqueNum.length];
21.         // initial dp[0][]
22.         for (int i = 0; i < uniqueNum.length; i++) {
23.             if (num[0] >= uniqueNum[i]) {
24.                 dp[0][i] = new CostTrack(num[0] – uniqueNum[i], -1);
25.                 continue;
26.             }
27.             dp[0][i] = new CostTrack(0, -1);
28.         }
29.         for (int i = 1; i < num.length; i++) {
30.             for (int j = 0; j < uniqueNum.length; j++) {
31.                 // Considering adding num[i] to the sorted array,
32.                 int diff = (num[i] >= uniqueNum[j]) ? (num[i] – uniqueNum[j])
33.                         : num[i];
34.                 dp[i][j] = new CostTrack(Integer.MAX_VALUE, -1);
35.                 for (int k = 0; k <= j; k++) {
36.                     if (dp[i – 1][k].cost + diff < dp[i][j].cost) {
37.                         dp[i][j].cost = dp[i – 1][k].cost + diff;
38.                         dp[i][j].from = k;
39.                     }
40.                 }
41.             }
42.         }
43.         // print result
44.         int result = -1, result_cost = Integer.MAX_VALUE;
45.         for (int i = 0; i < uniqueNum.length; i++) {
46.             if (dp[num.length – 1][i].cost < result_cost) {
47.                 result_cost = dp[num.length – 1][i].cost;
48.                 result = i;
49.             }
50.         }
51.         List<Integer> result_list = new ArrayList<Integer>();
52.         for (int i = num.length – 1; i >= 0; i–) {
53.             if (num[i] >= uniqueNum[result]) {
54.                 result_list.add(0, uniqueNum[result]);
55.                 result = dp[i][result].from;
56.             }
57.         }
58.         System.out.println(“sorted array:\t” + result_list.toString());
59.         return result_cost;
60.     }
61.     static class CostTrack {
62.         int cost;
63.         int from;
64.         public CostTrack(int cost, int from) {
65.             this.cost = cost;
66.             this.from = from;
67.         }
68.     }
69. }