d253. 00674 - Coin Change
Tags : DP 找零問題
Accepted rate : 1041人/1107人 ( 94% ) [非即時]
評分方式:
Strictly

最近更新 : 2015-08-28 14:39

Content

給你一個金額( n cents),請你回答共有多少種硬幣組合的方式。例如:n=11,那麼你可以有以下4種硬幣的組合:

  1. 1個 10 cent的硬幣加上1個 1 cent的硬幣
  2. 2個 5 cent的硬幣加上1個 1 cent的硬幣
  3. 1個 5 cent的硬幣加上6個 1 cent的硬幣
  4. 11個 1 cent的硬幣

p.s 美國的零錢共有以下5種硬幣以及其面值:

  • penny, 1 cent
  • nickel, 5 cents
  • dime, 10 cents
  • quarter, 25 cents
  • half-dollar, 50 cents

請注意:n=0 我們算他是有一種方式。

Input

每組測試資料1列,有1個整數n(0 <= n <= 7489),代表零錢的總金額(單位:cent)。

Output

對每組測試資料請輸出共有多少種硬幣組合方式。

Sample Input #1
0
17 
11
4
1000
2000
7489
Sample Output #1
1
6
4
1
801451
11712101
2146113925
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1M
Hint :
* 中文翻譯:Lucky 貓 
Tags:
DP 找零問題
出處:
UVa674 [管理者: pcsh710742 (ms0472904) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
26952 alison.acorn ... (aa w) d253
1411 2021-09-04 17:33
14007 yungshenglu1 ... (David Lu) d253
Coin Change
2468 2018-05-29 12:54