题目

给一个整数数组，调整每个数的大小，使得相邻的两个数的差小于一个给定的整数target，调整每个数的代价为调整前后的差的绝对值，求调整代价之和最小是多少。

注意事项

你可以假设数组中每个整数都是正整数，且小于等于100。

样例

对于数组[1, 4, 2, 3]和target=1，最小的调整方案是调整为[2, 3, 2, 3]，调整代价之和是2。返回2。

分析

动态规划，一个元素一个元素的调整，由于是要求相邻元素的差值，所以只和前一个相邻元素的值有关，所以只需要记录上一个调整的值就可以。
那么。dp[i][j]表示调整到第i个数时，此时，第i个数取值j,为代价和最小。
显然，假设dp[i-1][k]已知，则dp[i][j] = dp[i-1][k] + abs(j-A[i])
由于j和k都有多种可能取值，所以循环求解判断，k表示前一个数，j表示现在的数，假设j确定，那么k的取值就是在一个范围内，因为差值不能超过target。

代码

   public static int minAdjustmentCost(List<Integer> A,int target) {
       int n=A.size();
       int[][] f=new int[n+1][101];
        for (int i = 0; i <=n ; i++) {
            for (int j = 0; j <=100 ; j++) {
                f[i][j]=Integer.MAX_VALUE;
            }
        }
        for (int i = 0; i <=100 ; i++) {
            f[0][i]=0;
        }
        for (int i = 1; i <=n ; i++) {
            for (int j = 0; j <=100 ; j++) {
                if(f[i-1][j] !=Integer.MAX_VALUE){
                    for (int k = 0; k <=100 ; k++) {
                        //对于第一行让他变为0，初始化，当前的
                        if (Math.abs(j-k)<=target){
                            if(f[i][k]>f[i-1][j]+Math.abs(A.get(i-1)-k)){
                                f[i][k]=f[i-1][j]+Math.abs(A.get(i-1)-k);
                            }
                        }
                    }
                }
            }
        }
        int ans=Integer.MAX_VALUE;
        for(int i=0;i<=100;i++){
            if(f[n][i]<ans){
                ans=f[n][i];
            }
        }
        return ans;
    }