硬币找零，动态规划重新

我有理解这个问题背后的逻辑艰难的时间，这是经典的动态规划问题硬币找零，动态规划重新

 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个硬币或不但我不明白这两个州之间做了什么“+”。

对于如

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

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

来源

2015-07-19 bitshiftleft

好了，你还没有写你的状态吧！（i，j）表示仅使用i个硬币（从i到1）形成j作为总和的方式的数量。

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

有2种独立方法，使我可以代表这个国家是

1）让我们拿起个硬币，那么会发生什么吗？如果不允许重复，我需要使用i-1硬币的面额j-Denomination [i]。即，C（I，J）= C（I-1，J-面额[I]）

但是等等，我们缺少某些方面，即当不采取当前硬币

2）C （i，j）= C（i-1，j）

现在，因为它们都是独立的和详尽的，这两种状态构成了总的方式！

C（I，J）= C（I-1，J）+ C（I-1，J-面额[I]）

我将离开时允许你重复复发！

来源

2015-07-19 18:25:16

“现在，因为它们都是独立的和详尽的” - 这是我寻找的路线“。在中间使用'+'与我们在组合或是在组合中是一样的？即”这个或那个“方式 – bitshiftleft

是的！不管是这种方式还是那个!!没有其他可能的方式，也没有重复!! –

非常感谢...你帮了很多:) – bitshiftleft

硬币找零，动态规划重新

回答

相关问题