算法-数组|最小调整代价
【算法-数组|最小调整代价】给一个整数数组，调整每个数的大小，使得相邻的两个数的差不大于一个给定的整数target，调整每个数的代价为调整前后的差的绝对值，求调整代价之和最小是多少。
你可以假设数组中每个整数都是正整数，且小于等于100。
您在真实的面试中是否遇到过这个题？
是 样例
对于数组[1, 4, 2, 3]和target=1，最小的调整方案是调整为[2, 3, 2, 3]，调整代价之和是2。返回2。
class Solution {
public:
/*
* @param A: An integer array
* @param target: An integer
* @return: An integer
*/
int MinAdjustmentCost(vector &A, int target) {
// write your code here
// return MinAdjustmentCostDP(A, target);
// save history to avoid duplicate computing
vector> dp(A.size(), vector(101, -1));
return MinAdjustmentCostDFS(A, dp, target, 0, -1);
}
int MinAdjustmentCostDP(vector &A, int target) {
int n = A.size();
if (n == 0) {
return 0;
}
// adjust size max = 100 + k;
min = -k;
include 0
vector> dp(n + 1, vector(101, INT_MAX));
// init
dp[0] = vector(101, 0);
for (int i = 1;
i <= n;
i++) {
for (int j = 0;
j <= 100;
j++) {
for (int k = 0;
k <= 100;
k++) {
if (abs(j - k) <= target) {
dp[i][j] = min(dp[i - 1][k] + abs(j - A[i - 1]), dp[i][j]);
}
}
}
}
int minadjust = INT_MAX;
for (int j = 0;
j <= 100;
j++) {
if (minadjust > dp[n][j]) {
minadjust = dp[n][j];
}
}
return minadjust;
}
int MinAdjustmentCostDFS(vector &A, vector> &dp, int target, int sub, int lastvalue) {
if (sub == A.size()) {
return 0;
}
if (lastvalue >= 0 && dp[sub][lastvalue] != -1) {
return dp[sub][lastvalue];
}
int end = lastvalue < 0 ? 100 : min(lastvalue + target, 100);
int start = lastvalue < 0 ? 0 : max(lastvalue - target, 0);
int minadjust = INT_MAX;
for (int i = start;
i <= end;
i++) {
minadjust = min(abs(A[sub] - i) + MinAdjustmentCostDFS(A, dp, target, sub + 1, i), minadjust);
}
if (lastvalue >= 0) {
dp[sub][lastvalue] = minadjust;
}
return minadjust;
}
};
推荐阅读
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- 数组常用方法一
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- Java|Java基础——数组
- 《算法》-图[有向图]
- JS常见数组操作补充
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- 虚拟DOM-Diff算法详解