最低调整成本

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 的成本，如下所示：

 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]);

}