硬币找零问题动态规划求解的思路

Question

我正在学习动态规划并遇到了这个著名的 coins change problem。

解决这个问题的递归关系由

给出

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

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

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

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

从递归关系很容易理解(arr, sum - arr[i], i)在同一行翻译成DP[sum-arr[i]]。（因为i是一样的）

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

完整的二维矩阵解决方案如下所示。

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

但是给出的灵魂 here in method 2 仅使用一维数组，如下所示

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）

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

Answer 1

一维数组的解决方案只是重复使用您保存在单独行中的 space。这是可能的，因为那些 "older" 行不再使用。

以您代码中的这条语句为例：

int sumWithoutI = table[i - 1][j];

您可以验证这是您最后一次读取该值。下次您从 table 读取一个值时，它将具有更大的 i 值，或者 - 如果相同 - 具有更大的 j 值。所以有 "collapsing" 所有行在一起的空间，并用真正属于下一个 i 值（行）的新值覆盖数组值。

Answer 2

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

考虑填充一行 -- 第 0 个单元格的值为 1，所有其他单元格的开头值为 0。要更新单元格，我们需要查找同一行内的 table[i, sum - arr[i]]。对于 table[i - 1, sum]，我们需要查找上一行。我们不需要任何其他行。所以实际上我们只需要 2 行 space 并且我们可以选择将其中一行视为前一行，将另一行视为要填充的当前行。

现在考虑使用只有 2 行的 2 x (sum+1) table 来解决问题。考虑第 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 行。所以算法最终的space高效化身是——取单行大小(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

Answer 3

TL;DR：请注意，在您的 2D 循环中，当计算 table[i] 的条目时，您仅使用 table[i][...] 和 table[i - 1][...]。这应该给你一个提示，只存储 previous 和 current 行，并引导你将 space 减少到 1D数组。

首先，考虑一个更简单的递归来找到第 N 个斐波那契数，我们将 O(N) space 减少到 O(1) space:

对于重复F(n) = F(n - 1) + F(n - 2)

F[0] = 0
F[1] = 1

for(int i = 2; i <= N; i++) {
    F[i] = F[i - 1] + F[i - 2]
}

return F[N]

在这里，我们看到我们只使用循环的 最后 2 个值，不需要整个数组来存储所有值。

F0 = 0
F1 = 1
Fn = 1

for(int i = 2; i <= N; i++) {
    Fn = F0 + F1
    F0 = F1
    F1 = Fn
}

return Fn

我们现在对您的问题应用类似的归约，只是在一个更高的维度上。采用您的 2D 版本，我们将其修改为仅存储 2 行 table[i - 1]（如 tablePrev）和 table[i]（如 tableI）并保持更新。

 tablePrev = // Initialised to the 0th row

// All I did was replace table[i - 1][...] with tablePrev[...],
// and table[i][...] with tableI[...]
for (int i = 1; i < arr.length; i++) {
    tableI = tablePrev

    for (int j = 1; j <= sum; j++) {
        int sumWithI = j - arr[i-1] < 0 ? 0 : tableI[j - arr[i-1]];
        int sumWithoutI = tablePrev[j];
        tableI[j] = sumWithI + sumWithoutI;
    }

    tablePrev = tableI
}

就是这样。我们已将 space 缩减为一维数组 - 但我们使用了两个数组。对于这个特殊问题，现在很容易看出（由于 tableI 上更新的性质）您甚至不需要 tablePrev，只需重新使用 tableI，即可得出最终结果您在问题中提供的一维解决方案。

硬币找零问题动态规划求解的思路

Thought process for arriving at dynamic programming solution of Coins change problem

algorithm

dynamic-programming

coin-change