740 · 零钱兑换 2

给出不同面值的硬币以及总金额. 试写一函数来计算构成该总额的组合数量. 你可以假设每一种硬币你都有无限个.

一起战拖呀！

微信加【jiuzhang0607】备注【战拖】即可进入官方刷题群，团战offer！

你可以做出以下假设:

• 0 <= amount <= 5000

• 1 <= coin <= 5000

• 硬币种类不超过 500

• 结果保证符合 32 位符号整数

样例

样例1

输入: amount = 10 和 coins = [10] 
输出: 1

样例2

输入: amount = 8 和 coins = [2, 3, 8]
输出: 3
解释:
有3种方法:
8 = 8
8 = 3 + 3 + 2
8 = 2 + 2 + 2 + 2

 int change(int amount, vector<int> &coins) {
    vector<int> dp(amount + 1);
    dp[0] = 1;
    for (int& coin : coins) {
        for (int i = coin; i <= amount; i++) {
            dp[i] += dp[i - coin];
        }
    }
    return dp[amount];
}