DP - minimum adjustment cost

http://www.lintcode.com/en/problem/minimum-adjustment-cost/

Given an integer array, adjust each integers so that the difference of every adjacent integers are not greater than a given number target.

If the array before adjustment is A, the array after adjustment is B, you should minimize the sum of |A[i]-B[i]|

Example Given [1,4,2,3] and target = 1, one of the solutions is [2,3,2,3], the adjustment cost is 2 and it's minimal.

Return 2.

Note You can assume each number in the array is a positive integer and not greater than 100.

Solution:

State: d[i][v] means for the first i numbers, the minimum cost to adjust number i to v while satisfying the difference smaller than target

transform function:

d[i][v] = min (d[i-1][v'] + abs(a[i]-v), d[i][v]) (|v-v'| <= target)

time complexity O(n A target)

public static int MinAdjustmentCost(ArrayList<Integer> A, int target) {
10         // write your code here
11         if (A == null || A.size() == 0) {
12             return 0;
13         }
14         
15         // D[i][v]: 把index = i的值修改为v，所需要的最小花费
16         int[][] D = new int[A.size()][101];
17         
18         int size = A.size();
19         
20         for (int i = 0; i < size; i++) {
21             for (int j = 1; j <= 100; j++) {
22                 D[i][j] = Integer.MAX_VALUE;
23                 if (i == 0) {
24                     // The first element.
25                     D[i][j] = Math.abs(j - A.get(i));
26                 } else {
27                     for (int k = 1; k <= 100; k++) {
28                         // 不符合条件 
29                         if (Math.abs(j - k) > target) {
30                             continue;
31                         }
32                         
33                         int dif = Math.abs(j - A.get(i)) + D[i - 1][k];
34                         D[i][j] = Math.min(D[i][j], dif);
35                     }
36                 }
37             }
38         }
39         
40         int ret = Integer.MAX_VALUE;
41         for (int i = 1; i <= 100; i++) {
42             ret = Math.min(ret, D[size - 1][i]);
43         }
44         
45         return ret;
46     }
复制代码