[UVa]357:Let Me Count The Ways

這題是DP的找零錢問題。

有幾種組合的算法，
由於可能會有重覆算到的關係，
所以要先加入最小的零錢(此題是1cent)進去，
看看各個值(小於等於30000)假設最後一枚硬幣為此零錢能用幾種方法(其實是dp[該值-加入的零錢價值]種)找出來，
接著再把次小的零錢(此題是5cents)放進去，
看看各個值(小於等於30000)假設最後一枚硬幣為此零錢能用幾種方法(其實是dp[該值-加入的零錢價值]種)找出來，
這樣以此類推到最大的零錢，
這樣我在算最後一個零錢是5cents的組合的時候，
我只會找出1cent跟5cents的組合，
不會找出配上10cents啦...25cents啦...或是50cents之類的組合。
等到我在算最後一個零錢是10cents的組合的時候，
我只會找出10cents跟5cents跟1cent的組合，
不會找出配上25cents啦...或是50cents之類的組合。
(如果看不懂以上內容，可以翻閱關於DP找零錢問題的教學文章。)

P.S. 這題要用long long Orz...

[C](0.020)