Description

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

Notice

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

Example

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

Solution

dp[i][j]表示前i个数满足要求，且i个数取值j时的最小cost。
状态方程：dp[i][j] = dp[i-1][v] + |j-A[i]|，v表示第i-1个数的取值。要满足题目要求，v的取值范围应该在[max(j-target, 0), min(j+target, 100)]之间，故遍历这个范围内的v值取最小值方可找到最小cost的dp[i][j]
由于题目条件取值最大不超过100， 所以j的取值范围在[0, 100]之间。

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

        int[][] dp = new int[A.size()+1][101];
        for (int i = 1; i <= A.size(); i++) {
            for (int j = 0; j <= 100; j++) {
                dp[i][j] = Integer.MAX_VALUE;
                for (int v = j >= target ? j-target : 0; v <= j+target && v <= 100; v++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i-1][v] + Math.abs(j-A.get(i-1)));
                }
            }
        }

        int min = Integer.MAX_VALUE;
        for (int j = 0; j <= 100; j++) {
            min = Math.min(dp[A.size()][j], min);
        }

        return min;
    }
}