Q:http://uva.onlinejudge.org/external/3/357.html
經典的DP題
大意就是給你一個數字(0~30000)代表價格
這個價格可以用 1,5,10,25,50 這些價值的零錢來組合
問有多少種組合?
ex.
11元 = 11個1元 = 1個5元+6個1元 = 2個5元+1個1元 = 1個10元+1個1元
可以看到11元的組合有4種,所以輸出就是4,以此類推
解法很單純,先令個陣列,大小超過30000,用來存組合數
接著透過DP將0~30000元的組合數算出來,之後就按照input輸出答案
要注意30000元的組合數過多,所以這個陣列要令成long long int
至於DP的演算法講解,可以參考以下網站:
http://www.tcgs.tc.edu.tw/~sagit/cpp/q12.htm
這題超級重要啊@@
文章標籤
全站熱搜
留言列表
生活點滴 (3)
