给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
第一行两个个整数N和K, N代表需要达到的总金额,K代表有K种面额的硬币,用空格分隔。
第二行为K个整数a1,a2...ak,用空格分隔,代表K种面额的硬币。
一个整数代表用所给面额的硬币组合成N的方案数。
5 3 1 2 5
4
5 = 5
5 = 2 + 2 + 1
5 = 2 + 1 + 1 + 1
5 = 1 + 1 + 1 + 1 + 1
0<=N<=5000,1<=K<=500
1<=ai<=5000,
因为结果很大,请将其对1e9+7(1000000007)取模
#include<iostream> #include<vector> using namespace std; int change(int amount, vector<int>& coins) { vector<int> dp(amount + 1, 0); dp[0] = 1; for (int i = 0; i < coins.size(); i++) { // 遍历物品 for (int j = coins[i]; j <= amount; j++) { // 遍历背包 dp[j] = (dp[j] + dp[j - coins[i]]) % 1000000007; } } return dp[amount]; } int main(){ int n,k; cin >> n >> k; vector<int> coins(k); for (int i = 0; i < k; ++i) cin>>coins[i]; cout << change(n,coins) <<endl; return 0; }