给一个整数数组，调整每个数的大小，使得相邻的两个数的差不大于一个给定的整数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
