Minimum Adjustment Cost

Given an integer array, adjust each integers so that the difference of every adjcent 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.

Note

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

注意是positive number 所以j的起始值是1不是0 因为这个犯了好几次错....

state: dp[i][v] 表示前i个数, 第i个数调整为v 满足条件, 所需要的最小代价

function:如果i个数时j 那么第i-1个数k是要满足 Math.abs(j - k) < target的

dp[i][v] = Math.min(dp[i-1][k] +  Math.abs(j -A.get(i-1))) //第i个数时j 第i-1个数为k时候使代价最小

如果第i个数是j, 那么第i-1个数k只能在[lowerRange, UpperRange]之间，lowerRange=Math.max(0, j-target), upperRange=Math.min(99, j+target), 这样的话，transfer function可以写成： for (int p=lowerRange; p<= upperRange; p++) { 　　res[i][j] = Math.min(res[i][j], res[i-1][k] + Math.abs(j-A.get(i-1))); }

initial:dp[0][j]= 0

return: 满足条件的最小代价 Math.min(dp[m][j]) // 改变j的值找到最小的代价

public class Solution {

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

//Math.abs(j -A.get(i-1)))表示第i个数改为j所需代价

                }
            }
        }
        int result = Integer.MAX_VALUE;
        for (int j = 1 ; j <= 100; j++) {
            result = Math.min(result, dp[m][j]);
        }
        return result;
    }
}