我正在嘗試解決這個問題：給定一個整數數組，調整每個整數，使每個相鄰整數的差不大于給定的數字目標。如果調整前的數組為A，調整后的數組為B，則應盡量減少`|之和。A[i]-B[i]|。您可以假設數組中的每個數字都是正整數且不大于 100。`我看到了 dp 解，但不太明白遞推方程。public static int MinAdjustmentCost(ArrayList<Integer> A, int target) { // write your code here if (A == null || A.size() == 0) { return 0; } // D[i][v]: 把index = i的值修改為v，所需要的最小花費 int[][] D = new int[A.size()][101]; int size = A.size(); for (int i = 0; i < size; i++) { for (int j = 1; j <= 100; j++) { D[i][j] = Integer.MAX_VALUE; if (i == 0) { // The first element. D[i][j] = Math.abs(j - A.get(i)); } else { for (int k = 1; k <= 100; k++) { // 不符合條件 if (Math.abs(j - k) > target) { continue; } int dif = Math.abs(j - A.get(i)) + D[i - 1][k]; D[i][j] = Math.min(D[i][j], dif); } } } } int ret = Integer.MAX_VALUE; for (int i = 1; i <= 100; i++) { ret = Math.min(ret, D[size - 1][i]); } return ret;}有人可以向我解釋一下嗎？
1 回答
撒科打諢
TA貢獻1934條經驗 獲得超2個贊
您需要最小化調整成本，即增加/減少每個元素的值，使得每個相鄰元素之間的差異小于或等于target。dp 解決方案是嘗試所有可能的值并最小化有效值的成本（當abs(A[i]-A[i-1]) <= target）
第一件事是將第一個元素調整為 1-100 的成本，如下所示：
for (int i = 0; i < size; i++) {
for (int j = 1; j <= 100; j++) {
D[i][j] = Integer.MAX_VALUE; // fill with MAX_VALUE because we want to minimize
if (i == 0) {
// for the first element we just set the cost of adjusting A[i] to j
D[i][j] = Math.abs(j - A.get(i));
}
現在您需要D[0][j]將第一個元素調整為 的成本j。然后，對于每個其他元素，您再次循環（從k = 1到k = 100）其他元素并嘗試更改A[i]為j。然后檢查是否abs(k-j)有效（小于或等于target），然后您可以調整A[i]為j和A[i-1]以便k最小化D[i][j]。
這里的意思是改變到D[i][j]的成本，是改變到的成本。因此，對于每個并且如果它們有效（），那么您將它們添加在一起并最小化保存的值，以便您可以將其用于下一個元素，這是在此處完成的：A[i]jD[i-1][k]A[i-1]kkjabs(k-j)<=targetD[i][j]
else {
for (int k = 1; k <= 100; k++) {
// if abs(j-k) > target then changing A[i] to j isn't valid (when A[i-1] is k)
if (Math.abs(j - k) > target) {
continue;
}
// otherwise, calculate the the cost of changing A[i] to j and add to it the cost of changing A[i-1] to k
int dif = Math.abs(j - A.get(i)) + D[i - 1][k];
// minimize D[i][j]
D[i][j] = Math.min(D[i][j], dif);
}
}
最后，您需要在最后一個元素處從 1 循環到 100，并檢查哪個是所有元素中的最小值，這在此處完成：
int ret = Integer.MAX_VALUE;
for (int i = 1; i <= 100; i++) {
ret = Math.min(ret, D[size - 1][i]);
}
我覺得如果把初始化代碼和DP計算代碼分開會更容易理解，例如：
// fill the initial values
for (int i = 0; i < size; ++i) {
for (int j = 1; j <= 100; ++j) {
// on the first element just save the cost of changing
// A[i] to j
if (i == 0) {
DP[i][j] = abs(j-A.get(i));
} else {
// otherwise intialize with MAX_VALUE
D[i][j] = Integer.MAX_VALUE;
}
}
}
for (int i = 1; i < size; i++) {
for (int j = 1; j <= 100; j++) {
for (int k = 1; k <= 100; k++) {
// if abs(j-k) isn't valid skip it
if (Math.abs(j - k) > target) {
continue;
}
// if it is valid, calculate the cost of changing A[i] to j
// and add it to the cost of changing A[i-1] to k then minimize
// over all values of j and k
int dif = Math.abs(j - A.get(i)) + D[i - 1][k];
D[i][j] = Math.min(D[i][j], dif);
}
}
}
// calculate the minimum cost at the end
int ret = Integer.MAX_VALUE;
for (int i = 1; i <= 100; i++) {
ret = Math.min(ret, D[size - 1][i]);
}
添加回答
舉報
0/150
提交
取消