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 isA, the array after adjustment isB, you should minimize the sum of|A[i]-B[i]|

Notice

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

Example

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

Return2.

Solution 1: DFS

public int MinAdjustmentCost(ArrayList<Integer> A, int target) {
    if(A.size() == 0) {
        return 0;
    }
    return dfs(A, target, new ArrayList<Integer>(A), 0);
}
public int dfs(ArrayList<Integer> A,
               ArrayList<Integer> B,
               int target,
               int index) {
    if(index >= A.size()) {
        return 0;
    }
    int diff = 0;
    int min = Integer.MAX_VALUE;
    for(int i = 0; i <= 100; i++) {
        if(index != 0 && Math.abs(i - B.get(index - 1)) > target)
            continue;
        B.set(index, i);
        diff = Math.abs(i - A.get(index));
        diff += dfs(A, B, target, index + 1);
        min = Math.min(min, diff);
        B.set(index, A.get(index));
    }
    return min;
}

Solution 2: Memory Search.

public int MinAdjustmentCost(ArrayList<Integer> A, int target) {
    if(A.size() == 0) {
        return 0;
    }
    int[][] dp = new int[101][A.size()];
    for(int i = 0; i < 101; i++) {
        for(int j = 0; j < A.size(); j++) {
            dp[i][j] = -1;    
        }
    }
    return memory(A, target, new ArrayList<Integer>(A), 0, dp);   
}
public int memory(ArrayList<Integer> A, int target, ArrayList<Integer> B, int index, int[][] dp) {
    if(index == A.size()) {
        return 0;
    }
    int diff = 0, min = Integer.MAX_VALUE;
    for(int i = 0; i <= 100; i++) {
        if(index > 0 && Math.abs(i - B.get(index - 1)) > target) {
            continue;
        }
        if(dp[i][index] != -1) {
            diff = dp[i][index];
            min = Math.min(min, diff);
            continue;
        }
        B.set(index, i);
        diff = Math.abs(i - A.get(index));
        diff += memory(A, target, B, index + 1, dp);
        dp[i][index] = diff;
        min = Math.min(min, diff);
        B.set(index, A.get(index));
    }
    return min;
}

Solution 3:

public int MinAdjustmentCost(ArrayList<Integer> A, int target) {
    if(A.size() == 0) {
        return 0;
    }
    int[][] dp = new int[A.size()][101];
    int min = Integer.MAX_VALUE, diff = 0;
    for(int i = 0; i < A.size(); i++) {
        for(int j = 0; j < 101; j++) {
            dp[i][j] = Integer.MAX_VALUE;
            if(i == 0) {
                dp[i][j] = Math.abs(j - A.get(i));
            }
            else {
                for(int k = 0; k < 101; k++) {
                    if(Math.abs(j - k) > target) {
                        continue;
                    }
                    diff = Math.abs(j - A.get(i)) + dp[i - 1][k];
                    dp[i][j] = Math.min(dp[i][j], diff);
                }
            }
        }
    }
    for(int i = 0; i <= 100; i++) {
        min = Math.min(min, dp[A.size() - 1][i]);
    }
    return min;
}