找零錢問題

作者  l314 (紅蟲)                                          站內  P_RedBug
標題  [ACM]找零錢問題..
時間  Sat Sep 30 22:45:12 2006
───────────────────────────────────────

為什可以用dynamic programming
應該可以寫成數歸形式,但我不會..>,<

但解題的思維是...

先只考慮只有1 cent的組合
每個數字都只有一種

再加入考慮5cent的組合,
這時候從5-9的數字都會多了一種組合,(共兩種)
從10-14的數字會多兩種組合,因為它們可以分解為5+5,5+6,5+7...(共三種)
(而此時的5-9都是兩種組合)
從15-20的數字會多三種組合,因為他們可分解為5+10,5+11,5+12...(共四種)
(而此時的10-14都是三種組合)
以此類推...有趣的是,前面的數字變動,後面數字的變動就會被放大..

這時再加入考慮10cent的組合
這時候從10-19的數字都會多了一種組合,(共四種)
從20-30會多四種組合,因為他們可以分解為10+10,10+11,10+12,...(共九種)
............

以此類推再考慮加入25cent及50cent的組合...