最低调整成本

Question

我正在尝试解决这个问题：

给定一个整数数组，调整每个整数，使每个相邻整数的差不大于给定的数字目标。

如果调整前的数组为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;

}

有人可以向我解释一下吗？

Answer 1

您需要最小化调整成本，即增加/减少每个元素的值，使得每个相邻元素之间的差异小于或等于target。dp 解决方案是尝试所有可能的值并最小化有效值的成本（当abs(A[i]-A[i-1]) <= target）第一件事是将第一个元素调整为 1-100 的成本，如下所示：&nbsp;for (int i = 0; i < size; i++) {&nbsp; &nbsp; &nbsp; &nbsp; for (int j = 1; j <= 100; j++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; D[i][j] = Integer.MAX_VALUE; // fill with MAX_VALUE because we want to minimize&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (i == 0) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // for the first element we just set the cost of adjusting A[i] to j&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; D[i][j] = Math.abs(j - A.get(i));&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }现在您需要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 {&nbsp; &nbsp; for (int k = 1; k <= 100; k++) {&nbsp; &nbsp; &nbsp; &nbsp; // if abs(j-k) > target then changing A[i] to j isn't valid (when A[i-1] is k)&nbsp; &nbsp; &nbsp; &nbsp; if (Math.abs(j - k) > target) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; continue;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; // otherwise, calculate the the cost of changing A[i] to j and add to it the cost of changing A[i-1] to k&nbsp; &nbsp; &nbsp; &nbsp; int dif = Math.abs(j - A.get(i)) + D[i - 1][k];&nbsp; &nbsp; &nbsp; &nbsp; // minimize D[i][j]&nbsp; &nbsp; &nbsp; &nbsp; D[i][j] = Math.min(D[i][j], dif);&nbsp; &nbsp; &nbsp;}}最后，您需要在最后一个元素处从 1 循环到 100，并检查哪个是所有元素中的最小值，这在此处完成：int ret = Integer.MAX_VALUE;for (int i = 1; i <= 100; i++) {&nbsp; &nbsp; ret = Math.min(ret, D[size - 1][i]);}我觉得如果把初始化代码和DP计算代码分开会更容易理解，例如：// fill the initial valuesfor (int i = 0; i < size; ++i) {&nbsp; &nbsp; for (int j = 1; j <= 100; ++j) {&nbsp; &nbsp; &nbsp; &nbsp; // on the first element just save the cost of changing&nbsp; &nbsp; &nbsp; &nbsp; // A[i] to j&nbsp; &nbsp; &nbsp; &nbsp; if (i == 0) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; DP[i][j] = abs(j-A.get(i));&nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // otherwise intialize with MAX_VALUE&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; D[i][j] = Integer.MAX_VALUE;&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }}for (int i = 1; i < size; i++) {&nbsp; &nbsp; for (int j = 1; j <= 100; j++) {&nbsp; &nbsp; &nbsp; &nbsp; for (int k = 1; k <= 100; k++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // if abs(j-k) isn't valid skip it&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (Math.abs(j - k) > target) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; continue;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // if it is valid, calculate the cost of changing A[i] to j&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // and add it to the cost of changing A[i-1] to k then minimize&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // over all values of j and k&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int dif = Math.abs(j - A.get(i)) + D[i - 1][k];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; D[i][j] = Math.min(D[i][j], dif);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }}// calculate the minimum cost at the endint ret = Integer.MAX_VALUE;for (int i = 1; i <= 100; i++) {&nbsp; &nbsp; ret = Math.min(ret, D[size - 1][i]);}