题目描述
给一个整数数组，调整每个数的大小，使得相邻的两个数的差小于一个给定的整数target，调整每个数的代价为调整前后的差的绝对值，求调整代价之和最小是多少
你可以假设数组中每个整数都是正整数，且小于等于100
样例
对于数组[1, 4, 2, 3]和target=1，最小的调整方案是调整为[2, 3, 2, 3]，调整代价之和是2。返回2。
思路
DP。
动态规划一般是用数组表示结果集，每次新元素加入时动态更新数组的数据。所以首先就要明确怎么定义数组。
每个新元素，都可能会调整到1~100。所以考虑用一个二维数组，row对应n个元素，col为101（位置0没用，因为是正整数）
二维数组的意义是什么呢？
cost[i][j]表示第i个元素调整到位置j后，所需要付出的最小的代价和。所以其依赖于前一个元素调整到[j-target,j+target]范围内的最小代价和。
更新公式：
1
2
| // 当前元素到j的代价与上一个元素的代价之和，在上一个元素有效区间内的最小代价
cost[i][j] = Math.min(cost[i][j], cost[i-1][k]+tmpCost);
|
最后代价和会保存在cost[n-1][]中，找到最小值就是最小的代价和。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| public int MinAdjustmentCost(ArrayList<Integer> A, int target) {
// write your code here
int n = A.size();
int[][] cost = new int[n][101]; // A[i][j]：第i个元素移动到位置j时需要付出的最小代价和（算上之前的代价）
for(int i = 1; i <= 100; i++) {
cost[0][i] = Math.abs(i-A.get(0)); // 初始化第一个元素的代价
}
for(int i = 1; i < n; i++) { // 从第二个元素开始，DP代价数组
for(int j = 1; j <= 100; j++) {
cost[i][j] = Integer.MAX_VALUE; // 为了DP迭代服务
int tmpCost = Math.abs(A.get(i)-j); // 当前元素到位置j的代价
int min = Math.max(1, j-target); //min和max为上一个元素的代价数组起作用的范围
int max = Math.min(100, j+target);
for(int k = min; k <= max; k++) { // k表示在上一个元素起作用范围内的下标
// 动态规划当前元素到位置j的代价：
// 当前元素到j的代价与上一个元素的代价之和，在上一个元素有效区间内的最小代价
cost[i][j] = Math.min(cost[i][j], cost[i-1][k]+tmpCost);
}
}
}
// 求最小的总代价和
int res = cost[n-1][1];
for(int i = 2; i <= 100; i++) {
if(res > cost[n-1][i]) {
res = cost[n-1][i];
}
}
return res;
}
|
考察点