Lintcode 91. 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

Example 1:
 Input:  [1,4,2,3], target=1
 Output:  2

Example 2:
 Input:  [3,5,4,7], target=2
 Output:  1
 

Notice

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

Solution:
Since each number is between [1, 100], define dp[N][101] where dp[i][j] means for the min adjusting cost for number A[i] with its values changed to j. 
So the transit function is 
dp[i][j] = dp[i - 1][k] + abs(j - A[i]), where k >= target - j and k <= target + j

finally we return the dp[len - 1][j], where 1 <= j <= 100;

Code (Java):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

public class Solution {     /*      * @param A: An integer array      * @param target: An integer      * @return: An integer      */     public int MinAdjustmentCost(List<Integer> A, int target) {         if (A == null || A.size() == 0) {             return 0;         }                   int[][] dp = new int[2][101];         int old = 0;         int cur = 0;         for (int i = 1; i <= A.size(); i++) {             old = cur;             cur = 1 - cur;             for (int j = 1; j <= 100; j++) {                 int lo = Math.max(1, j - target);                 int hi = Math.min(100, j + target);                 dp[cur][j] = Integer.MAX_VALUE;                 for (int k = lo; k <= hi; k++) {                     dp[cur][j] = Math.min(dp[cur][j], dp[old][k] + Math.abs(A.get(i - 1) - j));                 }             }         }         int ans = Integer.MAX_VALUE;         for (int i = 1; i <= 100; i++) {             ans = Math.min(ans, dp[cur][i]);         }                   return ans;     } }