题目描述
给你六种面额1、5、10、20、50、100元的纸币，假设每种币值的数量都足够多，编写程序求组成N员（N为0-10000的非负整数）的不同组合的个数。
输入描述:
输入为一个数字N，即需要拼凑的面额
输出描述:
输出也是一个数字，为组成N的组合个数。
示例1
输入
5
输出
2
解题思路：
可以想象成一个完全背包问题，有6种钱币，总价值也即总重量为n，每种钱币都有无数件，求组合数。用dp[n]存放所有面额的组合数,c[j]存放所有的钱币面额，此时状态转移方程为：
dp[n] = dp[n] + dp[n - c[j]]
代码：
#include<iostream> using namespace std; int main() { int n; cin >> n; long long dp[10010] = { 0 }; //注意大于5000时会超过int范围，所以数组声明为long long int c[6] = { 1,5,10,20,50,100 }; dp[0] = 1; for (int j = 0; j < 6; j++) { for (int i = c[j]; i <= n; i++) { dp[i] += dp[i - c[j]]; } } cout << dp[n] << endl; return 0; }
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
