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 } 复制代码