2017-7-10
[1] 题目描述
给你六种面额1、5、10、20、50、100元的纸币，假设每种币值的数量都足够多，编写程序求组成N元(N为0~10000的非负整数)的不同组合的个数。
输入描述:
输入包括一个整数n(1≤n≤10000)
输出描述:
输出一个整数，表示不同的组合方案数。
输入例子:
1
输出例子:
1
[2] 题目解析
解: 题目解析
[1] 组合是指若两个子集的元素完全相同并顺序相异，它仍视为同一个组合。
[2] 求解取 i 种面额钱币填充用户输入的总额 n 的最大值。
[3] 联系经典的问题，即背包问题。
由题意可知:
| 总额 | 组合方案数 | 组合 |
|---|---|---|
| 1 | 1 | 1张1元 |
| 2-4 | 1-4 | 1-4 张1元 |
| 5 | 2 | 5×1元、1×5元 |
| 6-9 | 2 | （6-9）×1元、1×5元+（1-3）×1元 |
| 10 | 4 | 1×10元、2×5元、10×1元、1×5元+5×1元 |
| 20 | 10 | 1×20元、2×10元、4×5元、20×1元、1×10元+2×5元、1×10元+1×5元+5×1元、1×10元+10×1元、3×5元+5×1元、2×5元+10×1元、1×5元+15×1元 |
[3] 解题方案
求解 i 种面额钱币填充用户输入的总额 n 的最大值，即dp[j]=dp[j]+dp[j-coin[i]];
2017-7-10
只有我一个人计算过觉得上面的程序是错的吗？？？
2017-7-11
似乎这样写更合理一些！！！
