d253. 00674 - Coin Change
標籤 : DP 找零問題
通過比率 : 1015人/1080人 ( 94% ) [非即時]
評分方式:
Strictly

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

內容

給你一個金額( 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 我們算他是有一種方式。

輸入說明

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

輸出說明

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

範例輸入 #1
0
17 
11
4
1000
2000
7489
範例輸出 #1
1
6
4
1
801451
11712101
2146113925
測資資訊:
記憶體限制: 512 MB
提示 :
* 中文翻譯:Lucky 貓 
標籤:
DP 找零問題
出處:
UVa674 [管理者: pcsh710742 (ms0472904) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
26952 alison.acorn ... (aa w) d253
1339 2021-09-04 17:33
14007 yungshenglu1 ... (David Lu) d253
Coin Change
2390 2018-05-29 12:54