首页 > 代码库 > 美团2017秋招笔试题 拼凑钱币
美团2017秋招笔试题 拼凑钱币
给你六种面额 1、5、10、20、50、100 元的纸币,假设每种币值的数量都足够多,编写程序求组成N元(N为0~10000的非负整数)的不同组合的个数。
输入描述:
输入包括一个整数n(1 ≤ n ≤ 10000)
输出描述:
输出一个整数,表示不同的组合方案数设f[i][j]为使用a[0]-a[i]的面额凑到j元的不同组合个数
#include <iostream> #include <cstring> using namespace std; int a[6] = {1,5,10,20,50,100}; long long f[6][10001]; int main(){ int n; cin >> n; memset(f, 0, sizeof(f)); for(int j = 0; j <= n; j++){ f[0][j] = 1; } for(int i = 1; i < 6; i++){ for(int j = 1; j <= n; j++){ for(int k = 0; k <= j/a[i]; k++){ f[i][j] += f[i-1][j-k*a[i]]; } } } cout << f[5][n] << endl; return 0; }
美团2017秋招笔试题 拼凑钱币
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。