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, int target, ArrayList<Integer> B, int index) {
    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;
        }
        B.set(index, i);
        diff = Math.abs(i - A.get(index));
        diff += dfs(A, target, B, index + 1);
        min = Math.min(min, diff);
        B.set(index, A.get(index));
    }
}

Solution 2: Memory Search.

public int MinAdjustmentCost(ArrayList<Integer> A, int target) {
    if(A.size() == 0) {
        return 0;
    }
    int[][] M = new int[101][A.size()];
    for(int i = 0; i < 101; i++) {
        for(int j = 0; j < A.size(); j++) {
            M[i][j] = -1;
        }
    }
    return dfs(A, target, new ArrayList<Integer>(A), 0, M);
}
public int dfs(ArrayList<Integer> A, int target, ArrayList<Integer> B, int index, int[][] M) {
    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(M[i][index] != -1) {
            diff = M[i][index];
            min = Math.min(diff, min);
            continue;
        }

        B.set(index, i);
        diff = Math.abs(i - A.get(index));
        diff += dfs(A, target, B, index + 1, M);
        min = Math.min(min, diff);
        M[i][index] = diff;
        B.set(index, A.get(index));
    }
    return min;
}

Solution 3: DP.

public int MinAdjustmentCost(ArrayList<Integer> A, int target) {
        // write your code here
        if(A.size() == 0)
            return 0;
        int[][] M = new int[A.size()][101];
        int min = Integer.MAX_VALUE;

}