币变，再谈动态规划

Question

我很难理解这个问题背后的逻辑，这是经典的动态规划问题

     Coin Change is the problem of finding the number 
     of ways of making changes for a particular amount of cents, n, 
     using a given set of denominations d1,d2,..dm;

我知道递归是如何工作的，比如拿第m个硬币或not.But我不明白'+'在这两种状态之间做了什么

例如

        C(N,m)=C(N,m-1)+C(N-dm,m)
                       ^
                       |

问题可能很愚蠢，但我还是想知道，这样我才能有更好的understanding.Thanks

Answer 1

好吧，你的州没写对！硬币变化：

令 C(i,j) 表示仅使用 i 个硬币（从 i 到 1）形成 j 的总和的方法数。

现在要获得递归函数，您必须定义转换或状态变化，或者可能只是用较低的值来表达给定的表达式！！

有 2 种独立的 方式可以表示这种状态，它们是

1) 让我们拿起第 i 个硬币，然后会发生什么？如果不允许重复，我需要面额 j-Denomination[i] 和 i-1 个硬币。即 C(i,j)= C(i-1,j-Denominations[i])

但是等等，我们错过了一些方法，即当我们不拿当前硬币时

2) C(i,j)=C(i-1,j)

现在由于它们都是独立且详尽的，这两种状态构成了方法的总数！！！

C(i,j)=C(i-1,j)+C(i-1,j-面额[i])

如果您允许重复，我会离开重复！

币变，再谈动态规划

Coin change,dynamic programming revisited

dynamic-programming