凑硬币

[编程题]凑硬币

热度指数：220 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

输入描述:

第一行两个个整数N和K， N代表需要达到的总金额，K代表有K种面额的硬币，用空格分隔。

第二行为K个整数a1,a2...ak，用空格分隔，代表K种面额的硬币。

输出描述:

一个整数代表用所给面额的硬币组合成N的方案数。

示例1

输入

5 3
1 2 5

输出

说明

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)取模

算法知识视频讲解

牛客402106308号

#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;
}

发表于 2021-08-17 18:05:27 回复(0)