我正在尝试理解硬币找零问题背后的动态规划,其中一个人应该计算在给定一组硬币的情况下为一个面额找零的方案数。每种硬币都有无限多个。
这个算法来自于geeks4geeks网页上的这个页面。该算法如下所示(其中N代表面额,dp是大小为N+1的数组):
我不理解这里的DP是如何工作的,以及子问题是什么。
编辑:我查看了其他相关问题,但没有提到上述算法。之前的问题中讨论了2-D DP解决方案。
这个算法来自于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解决方案。
table[:]
等同于第一个中的table[:][j]
。其余部分相同。他们交换了索引,可能会让事情变得混乱。在 DP 中,注意到你只需要回顾一行,因此你不需要存储整个矩阵是很常见的,有时你会将当前和上一行分别存储,但在这里,你可以随着进程进行而覆盖。 - Bernhard Barker