硬币找零问题动态规划解的思考过程

Question

我正在学习动态编程并遇到了这个著名的硬币找零问题。

解决这个问题的递归关系由下式给出

countCoinsChangeRec(arr, sum - arr[i], i) + countCoinsChangeRec(arr, sum, i - 1);

优化问题的最简单方法是存储子问题的解。所以我Map为 的每个值维护了一个(sum,i)。不再解决同样的问题。

        String key = sum + ":" + i;    
        Integer memoizedVal = results.get(key);
        if (memoizedVal != null) {
            return memoizedVal;
        }

下一级优化是有一个二维表，n X sum其中 n 是集合中的元素数。

从(arr, sum - arr[i], i)转化为DP[sum-arr[i]]同一行的递归关系很容易理解。（因为i是相同的）

并(arr, sum, i - 1)转换为DP[i-1]（列中的上一行sum）。

带有 2D 矩阵的完整解决方案如下所示。

public static int countWaysDP2D(int[] arr, int sum) {
    int[][] table = new int[arr.length][sum + 1];
    table[0][0] = 1;

    for (int i = 1; i <= sum; i++) {
        table[0][i] = 0;
    }

    for (int j = 1; j < arr.length; j++) {
        table[j][0] = 1;
    }

    for (int i = 1; i < arr.length; i++) {
        for (int j = 1; j <= sum; j++) {
            int sumWithI = j - arr[i-1] < 0 ? 0 : table[i][j - arr[i-1]];
            int sumWithoutI = table[i - 1][j];
            table[i][j] = sumWithI + sumWithoutI;
        }
    }
    return table[arr.length - 1][sum];
}

但是方法2中给出的soultion 只使用一维数组，如下所示

public static int countWaysDP1D(int[] arr, int sum) {
    int[] table = new int[sum + 1];
    table[0] = 1;

    for (int i = 0; i < arr.length; i++) {
        for (int j = arr[i]; j <= sum; j++) {
            table[j] += table[j - arr[i]];
        }
    }
    return table[sum];
}

仅使用一维数组背后的逻辑是什么？我测试了许多输入值，结果与二维数组相同。二维数组如何转换为一维数组？

我的意思是所有的初始条件都去哪儿了？（0th row和0th column）

对于jth for 循环，为什么它从j数组中的第 th 个元素开始迭代直到sum递增1？很难想象所有这些。有人可以逐步解释这种转变吗？

Answer 1

从递推关系来看countCoinsChangeRec(arr, sum - arr[i], i) + countCoinsChangeRec(arr, sum, i - 1);，显然需要一定大小的二维数组/表len(arr) x (sum+1)来存储结果。我们将从表格的左上角到右下角顺序填充表格，我们的答案是右下角单元格的值。您需要两个值来填充表格的每个单元格table[i, sum - arr[i]] and table[i - 1, sum]。

考虑填充一行——第 0 个单元格的值为 1，所有其他单元格在开始时的值为 0。要更新单元格，我们需要查找table[i, sum - arr[i]]同一行中的单元格。对于table[i - 1, sum]，我们需要查找前一行。我们不需要任何其他行。所以实际上我们只需要 2 行空间，我们也可以将其中一行视为前一行，另一行视为正在填充的当前行。

现在考虑使用2 x (sum+1)只有 2 行的表来解决问题。考虑第 1 行是当前正在填充的行，第 0 行是已填充的上一行。假设 arr = [2, 3, 7]。因此，您按如下方式填充第 1 行。

table[1, 0] = table[0, 0]  
table[1, 1] = table[0, 1]
table[1, 2] = table[0, 2]
table[1, 3] = table[1, 0] + table[0, 3]
table[1, 4] = table[1, 1] + table[0, 4]
table[1, 5] = table[1, 2] + table[0, 5]
...

观察上述方程后，计算第 1 行的另一种方法是将第 0 行复制到未填充的第 1 行，然后填充第 1 行，如下所示

Copy row 0 onto row 1

table[1, 3] += table[1, 0]
table[1, 4] += table[1, 1]
table[1, 5] += table[1, 2]

我们可以重复使用第 0 行本身，而不是将第 0 行复制到未填充的第 1 行。所以该算法最终的空间高效化身是——取大小为(sum+1)的单行。将 row[0] = 1 指定为基本条件。我们填充第 0 行或任何其他行的方式没有区别，因为我们现在所做的唯一查找是在同一行内，如上所示。

// Pseudo code
create row of size (sum+1) 

row[0] = 1 // base condition

fill rest of the row with zeros

for element in arr:   /* for (int i = 0; i < arr.length; i++) */
    from column j where j - element >= 0 to end of row /* int j = arr[i]; j <= sum; j++ */
    row[j] += row[j-element]

return last element of row