给一个整数数组，调整每个数的大小，使得相邻的两个数的差不大于一个给定的整数target，调整每个数的代价为调整前后的差的绝对值，求调整代价之和最小是多少。
你可以假设数组中每个整数都是正整数，且小于等于100。

在线评测地址： 领扣题库官网

样例1：
输入:  [1,4,2,3], target=1
  输出:  2

样例2：
输入:  [3,5,4,7], target=2
        输出:  1

算法：dp

思路
已知每个整数范围[1,100]，那么对于每个元素，为了调整到该元素和与之相邻的元素的差不大于target，该元素调整的范围就在[1,100]。所以对于数组A[]的每一位元素，我们都需要进行[1,100]范围内的可能状态的转移。
令dpi表示元素A[i]=j时，A[i]与A[i-1]差值不大于target所需要付出的最小代价。
当A[i]=j时，可行的A[i-1]的范围为[max(1, j - target)，min(100, j + target)]。而dpi为所有可行的A[i-1]中，花费代价最小的一种可能，再加上A[i]调整到 j 所需花费abs(j - A[i])。
当A[i]=j时，k在[max(1, j - target)，min(100, j + target)]范围内时，我们可以写出以下式子：
1.临界值：
dp0 = abs(j - A[0])
2.状态转移方程：
dpi = min(dpi, dpi - 1 + abs(j - A[i]))
最后在所有最后一位的可能解dpn-1中的最小值，就是我们所求的最小代价。

复杂度

假设数组长度为n
空间复杂度O(10000*n)
时间复杂度O(n^2)

题解：

public class Solution {
    /*
     * @param A: An integer array
     * @param target: An integer
     * @return: An integer
     */
    public int MinAdjustmentCost(List<Integer> A, int target) {
        int n = A.size();
        // dp[i][j]表示元素A[i]=j时，A[i]与A[i-1]差值不大于target所需要付出的最小代价
        int[][] dp = new int[n][101];
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= 100; j++) {
                // 初始化为极大值
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= 100; j++) {
                if (i == 0) {
                    // 临界值：第一个元素A[0]调整为j的代价 
                    dp[0][j] = Math.abs(j - A.get(0));
                }
                else {
                    // left为A[i]=j时，A[i-1]与A[i]差值不大于target的A[i-1]最小值
                    // right为A[i]=j时，A[i-1]与A[i]差值不大于target的A[i-1]最大值
                    int left = Math.max(1, j - target);  
                    int right = Math.min(100, j + target);  
                    for (int k = left; k <= right; k++) {
                        // 当A[i-1]=k时，答案为A[i-1]=k的代价dp[i-1][k]，加上A[i]=j的调整代价abs(j-A[i])
                        dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + Math.abs(j - A.get(i))); 
                    }
                }
                
            }
        }
        int mincost = Integer.MAX_VALUE;
        for (int i = 1; i <= 100; i++) {
            mincost = Math.min(mincost, dp[n - 1][i]);
        }
        return mincost;
    }
}

更多题解参考：九章官网solution