算法：零钱兑换 - 计算找零的方式数量

Question

我正在尝试理解硬币找零问题背后的动态规划，其中一个人应该计算在给定一组硬币的情况下为一个面额找零的方案数。每种硬币都有无限多个。

这个算法来自于geeks4geeks网页上的这个页面。该算法如下所示（其中N代表面额，dp是大小为N+1的数组）：

dp[0] = 1
for each coin c:
    for i from c to N:
        if i >=  c:
            dp[i] += dp[i-c]

我不理解这里的DP是如何工作的，以及子问题是什么。

编辑：我查看了其他相关问题，但没有提到上述算法。之前的问题中讨论了2-D DP解决方案。

- silent_dev

---

那个算法是对该链接中给出的先前2D DP算法的简化。如果您查看先前算法中引用其他索引的方式，应该很容易看出可以以这种方式简化它。这与以子问题为思考单位不太相关，而是要考虑简化。 - Bernhard Barker

我无法理解这个简化，所以才请求帮助。谢谢！ - silent_dev

基本上，第二个中的 table[:] 等同于第一个中的 table[:][j]。其余部分相同。他们交换了索引，可能会让事情变得混乱。在 DP 中，注意到你只需要回顾一行，因此你不需要存储整个矩阵是很常见的，有时你会将当前和上一行分别存储，但在这里，你可以随着进程进行而覆盖。 - Bernhard Barker

Answer 1

你可以将这种方法视为解决C个子问题，其中C是硬币的数量。

子问题c包括“可以用包括硬币c在内但不包括任何更大价值的硬币来制造哪些值”。

基本子问题变成了“没有硬币可以制造哪些值”，答案只是值0。

然后，为了解决每个附加子问题，我们可以通过迭代数组来标记值，如果它们由以前硬币值的某个值加上当前值的一些硬币数量组成，则可能性存在。

由于我们在原地更新DP数组，因此事实证明我们只需要考虑向数组中的每个位置添加一个当前值的硬币。

- Peter de Rivaz