主題

ZeroJudge - d133: 00357 - Let Me Count The Ways 解題心得

Not In My Back Yard | 2021-01-15 00:00:05 | 巴幣 0 | 人氣 24

題目連結:


題目大意:
已知有 5 種貨幣幣值:1 分、 5 分、 10 分、 25 分以及 50 分。

輸入有多列,每列給定一整數 n (0 ≦ n ≦ 30000),代表金錢額度 n (單位:分)。試問有多少種硬幣組合方式可以組成 n ?

當方法數只有一種時請輸出:
There is only 1 way to produce n cents change.
大於一種則輸出:
There are 方法數 ways to produce n cents change.
參見範例輸出。



範例輸入:
17
11
4


範例輸出:
There are 6 ways to produce 17 cents change.
There are 4 ways to produce 11 cents change.
There is only 1 way to produce 4 cents change.


解題思維:
典型的硬幣問題,參見這題

不過這題不是求額度 n 的金錢最少可以用幾個硬幣,而是問有多少種方式。所以求解的過程不是取最小值,直接加上先前的方法數即可。還有一點要注意的是,因為這題額度可以到 30000,其方法數已經超過 2 ^ 31 ,所以對於 C++ 等語言請使用 long long 等型態儲存方法數。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作