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):

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;
    }
}