[Lintcode]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

.

分析：动态规划或者递归算法。动态规划:res[i][j]代表在i位置上换成j的cost。

public class Solution {
    /**
     * @param A: An integer array.
     * @param target: An integer.
     */
    public int MinAdjustmentCost(ArrayList<Integer> A, int target) {
        if(A == null || A.size() == 0) return 0;
        
        int[][] res = new int[A.size()][101];
        for(int i = 0; i < A.size(); i++) {
            for(int j = 1; j <= 100; j++) {
                res[i][j] = Integer.MAX_VALUE;
                if(i == 0) {
                    res[i][j] = Math.abs(A.get(i) - j);
                } else {
                    for(int k = 1; k <= 100; k++) {
                        if(Math.abs(j - k) > target) continue;
                        int diff = res[i - 1][k] + Math.abs(A.get(i) - j);
                        res[i][j] = Math.min(res[i][j], diff);
                    }
                }
            }
        }
        int ret = Integer.MAX_VALUE;
        for (int i = 1; i <= 100; i++) {
            ret = Math.min(ret, res[A.size() - 1][i]);
        }
         
        return ret;
    }
}
           

递归算法超时：

public class Solution {
    /**
     * @param A: An integer array.
     * @param target: An integer.
     */
    public int MinAdjustmentCost(ArrayList<Integer> A, int target) {
        if(A == null || A.size() == 0) return 0;
        
        return helper(A, new ArrayList<Integer>(A), 0, target);
    }
    
    int helper(ArrayList<Integer> A, ArrayList<Integer> B, int index, int target) {
        if(index >= B.size()) {
            return 0;
        }
        int min = Integer.MAX_VALUE;
        int diff = 0;
        
        for(int i = 0; i <= 100; i++) {
            if(index != 0 && Math.abs(B.get(index - 1) - i) > target) {
                continue;
            }
            B.set(index, i);
            diff = Math.abs(A.get(index) - i);
            diff += helper(A, B, index + 1, target);
            min = Math.min(min, diff);
            B.set(index, A.get(index));
        }
        
        return min;
    }
}