91. 最小调整代价
描述
给一个整数数组，调整每个数的大小，使得相邻的两个数的差不大于一个给定的整数target，调整每个数的代价为调整前后的差的绝对值，求调整代价之和最小是多少。
你可以假设数组中每个整数都是正整数，且小于等于100。
样例 1：
输入:
[1,4,2,3], target=1
输出:
2
样例 2：
输入:
[3,5,4,7], target=2
输出:
1
原题传送门
文章目录
91. 最小调整代价描述样例 1：样例 2：
题解最后说两句声明
题解
public class Solution {
public int MinAdjustmentCost(List
<Integer> A
, int target
) {
int size
= A
.size();
int[][] dp
= new int[size
][101];
for (int i
= 0; i
< dp
.length
; ++i
) {
for (int j
= 1; j
<= 100; ++j
) {
dp
[i
][j
] = Integer
.MAX_VALUE
;
}
}
for (int i
= 0; i
< size
; ++i
) {
for (int j
= 1; j
<= 100; ++j
) {
if (i
== 0) {
dp
[i
][j
] = Math
.abs(j
- A
.get(i
));
} else {
int left
= Math
.max(1, j
- target
);
int right
= Math
.min(100, j
+ target
);
for (int k
= left
; k
<= right
; ++k
) {
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
[size
- 1][i
]);
}
return minCost
;
}
}
最后说两句
非常感谢你阅读本文章，如果你觉得本文对你有所帮助，请留下你的足迹，点个赞，留个言，多谢~
作者水平有限，如果文章内容有不准确的地方，请指正。
希望小伙伴们都能每天进步一点点。
声明
本文由二当家的白帽子博客原创，转载请注明来源，谢谢~
