UVA-674 - Coin Change

• UVa Online Judge 解題結果請於 Submit 後，參閱 uHunt。
• 如果你有任何建議與指教，歡迎於下方留言一起討論喔！
• 相同題目：ZOJ-d253

題意概要

題目給定一個美金金額 ($n$ cents)，試問：總共有多少種硬幣組合的方式。例如：當 $n = 11$ 時，則可以有以下 $4$ 種組合方式：($n = 0$ 亦是有一種組合方式)

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 硬幣

• 分析：本題為「動態規劃 (Dynamic Programming; DP)」的基本題型。此題的硬幣沒有限制個數，所以不需要紀錄哪些硬幣已經使用過。這一類「找硬幣組合情形」的題目最重要的觀念是：如果「金額 $i$ 減去使用某種硬幣 $v$」後可以被可以被組合出來 (即：能用可以使用的硬幣組合)，則該金額一定可以被組合出來。

Input

The input file contains any number of lines, each one consisting of a number for the amount of money in cents.

Output

For each input line, output a line containing the number of different ways of making changes with the above $5$ types of coins.

Sample Input

11
26

Sample Output

4
13