lintcode最小调整代价
程序员文章站
2022-07-05 12:59:34
...
题目:
给一个整数数组,调整每个数的大小,使得相邻的两个数的差不大于一个给定的整数target,调整每个数的代价为调整前后的差的绝对值,求调整代价之和最小是多少。
假设数组中每个整数都是正整数,且小于等于100。
样例:
对于数组[1, 4, 2, 3]和target=1,最小的调整方案是调整为[2, 3, 2, 3],调整代价之和是2。返回2。
解题思路:
欲使|A(i)-A(i+1)|<=target
则A(i+1)-target<=A(i)<=target+A(i+1)
又因为0<=A(n)<=100
所以max(0,A(i+1)-target)<=A(i)<=min(100,target+A(i+1))
由于题目中要求数组A中每个数都小于等于100,所以我们可以构建一个(n,100)的矩阵Z,Z(i,j)表示A(i)调整为j的花费与A(i-1)调整为j-target<=A(i)<=target+j的最小花费之和。以样例为例,首先构建一个矩阵Z如下:
0 | 1 | 2 | 3 | 4 | |
---|---|---|---|---|---|
1 | 1 | 0 | 1 | 2 | 3 |
4 | 4 | 3 | 2 | ||
2 | |||||
3 |
其中Z(1,2)表示A(1)=4调整为1花费与A(0)=1调整为2-1至2+1的最小花费之和,也就是满足题目要求的前两个数的最小花费。
代码:
public int MinAdjustmentCost(List<Integer> A, int target) {
int result = 0;
int len = A.size();
if(len <= 1) {
return result;
}
int[][] cost = new int[len][100];
for(int i=0;i<100;i++) {
cost[0][i] =Math.abs(A.get(0)-i);
}
for(int i=1;i<len;i++) {
for(int j=0;j<100;j++) {
int up = Math.min(99, j+target);
int low = Math.max(0, j-target);
int diff = Math.abs(A.get(i)-j);
cost[i][j] = Integer.MAX_VALUE;
for (int k = low; k <= up; k++) {
cost[i][j] = Math.min(cost[i][j], cost[i-1][k] + diff);
}
}
}
result = Integer.MAX_VALUE;
for(int i=0;i<100;i++) {
result = Math.min(cost[len-1][i], result);
}
return result;
}