原题网址：https://www.lintcode.com/problem/minimum-adjustment-cost/description
描述
给一个整数数组，调整每个数的大小，使得相邻的两个数的差不大于一个给定的整数target，调整每个数的代价为调整前后的差的绝对值，求调整代价之和最小是多少。
你可以假设数组中每个整数都是正整数，且小于等于100。
您在真实的面试中是否遇到过这个题？
样例
对于数组[1, 4, 2, 3]和target=1，最小的调整方案是调整为[2, 3, 2, 3]，调整代价之和是2。返回2。
标签
背包问题
LintCode 版权所有
动态规划(DP)
思路：动态规划。
dp[i][j]表示调整到第 i 个数时，第 i 个数取值 j 为代价和最小。【意思是，第 i 个数取值 j 时，0~i 子数组的调整代价和最小是多少，不是单个数的调整代价最小】
如何计算第 i 个数取值 j 时，代价和最小值是多少呢？
显然，假设dp[i-1][k]已知，则dp[i][j] = dp[i-1][k] + abs(j-A[i])。对每个 j 来说，abs（ j-A[i] ）可以确定，但 dp[i-1][k] 却随着 k 值变化有多种可能，所以要找到那个最小值。对于确定的 j 来说，k的取值范围也确定了，因为二者差值小于target。所以可以在满足条件的k值里寻找dp[i-1][k]的最小值。【k 表示前一个数，j表示现在的数。假设 j 确定，那么 k 的取值就是在一个范围内，因为差值不能超过target。】
参考此文
这样，计算到最后一个元素时，每个 j 都有一个对应的最小代价和， 找出其中最小的，就是整个数组的最小代价和了。
AC代码：
class Solution { public: /* * @param A: An integer array * @param target: An integer * @return: An integer */
int MinAdjustmentCost(vector<int> &A, int target) { // write your code here
int size=A.size(); if (size<2) { return 0; } vector<vector<int>> dp(size,vector<int>(101,INT_MAX));//返回最后一行最小值，所以初值取int最大值，避免列索引为0的元素的干扰;
for (int i=0;i<size;i++) { for (int j=1;j<101;j++)//数组元素取值1~100;
{ if (i==0) { dp[i][j]=abs(j-A[i]); } else { //j值固定后，k取值范围随之固定;
for (int k=max(1,j-target);k<=min(j+target,100);k++)//注意循环条件是小于等于;
{ dp[i][j]=min(dp[i][j],abs(j-A[i])+dp[i-1][k]); } } } } /*int res=INT_MAX; for (int i=1;i<101;i++) { res=min(res,dp[size-1][i]); }*/
int res=*min_element(dp[size-1].begin(),dp[size-1].end()); return res; } };
代码实现时有几处需要注意：
1. j的取值范围。
按照题意数组元素的取值范围是【1，100】，所以定义dp时列尺寸可以为101，舍弃掉 j 为0的那列不再计算。
虽然不计算dp【i】【0】，但要防止最后求dp最后一行最小值时的干扰，所以可以将dp数组初值全部赋值为INT_MAX。也可以将数组初值赋值为0，中间二重循环时再临时赋值INT_MAX，最后计算最后一行最小值时将第一个元素去除。说了半天其实是写代码时要注意逻辑严谨。
以及，j的取值可以进一步优化。由题意，调整数组使其相邻元素差值在一定范围内，意思是减小元素间的差异，“大的变小小的变大”，所以 j 最大值（也即dp列尺寸）可以直接定义为数组A的最大元素值。
2. j值固定后，k的取值范围是如何确定的
我们知道，1≤k≤100（或者A的最大元素）且abs（k-j）≤ target，好了，k取值范围可以确定了，取上述两个不等式的交集。
abs（k-j）≤ target可以化简为：k>j，k ≤ target+j；k ≤ j，k ≥ j-target。求交集后，max(1,j-target) ≤ k ≤ max(j+target,100)，画个区间图就明白了。
PS：虽然一开始想到了用动态规划求解，但具体怎么做还是一筹莫展，最后还是参照了网上的答案才做出来，这种题不看别人的解法绝对想不出来用二维dp数组来解决，还在那里傻兮兮的推导一维dp的状态转移方程……
其他参考：
Lintcode: Minimum Adjustment Cost 解题报告 这个答案没怎么细看……