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.

Have you met this question in a real interview?

Yes

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.

类似背包类的动态规划，将值带入状态，

f[i][v]代表前i个元素中将第i个元素变为v的最小调整代价

这里需要我们去枚举v和v'的值,并且保持 v - v' <= target (v是第i个元素调整的目标值， 而v'是第 i - 1个元素调整的目标值）

(因为题目中说出元素的值不超过100，并且是正数，所以v的范围在0-100

public class Solution {
    /*
     * @param A: An integer array
     * @param target: An integer
     * @return: An integer
     */
    public int MinAdjustmentCost(List<Integer> A, int target) {
        // write your code here
        if (A == null || A.size() == 0) {
            return 0;
        }

        int[][] f = new int[A.size() + 1][101];
        for (int i = 1; i <= A.size(); i++) {
            for (int j = 0; j <= 100; j++) {
                f[i][j] = Integer.MAX_VALUE;
            }
        }


        for (int i = 1; i <= A.size(); i++) {
            for (int j = 0; j <= 100; j++) {
                if (f[i - 1][j] == Integer.MAX_VALUE) {
                    continue;
                }
                for (int v = 0; v <= 100; v++) {
                    if (Math.abs(j - v) <= target) {
                        f[i][v] = Math.min(f[i][v], f[i - 1][j] + Math.abs(A.get(i - 1) - v));
                    }
                }
            }
        }

        int ans = Integer.MAX_VALUE;
        for (int i = 0; i <= 100; i++) {
            ans = Math.min(ans, f[A.size()][i]);
        }
        return ans;

    }
}