硬幣找零，動態規劃重新

我有理解這個問題背後的邏輯艱難的時間，這是經典的動態規劃問題硬幣找零，動態規劃重新

 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

硬幣找零，動態規劃重新

回答

相關問題