518. 零钱兑换 II

零钱兑换 II

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。 
题目数据保证结果符合 32 位带符号整数。

样例

---

Example

示例 1：
**输入：**amount = 5, coins = [1, 2, 5]
**输出：**4
**解释：**有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2：
**输入：**amount = 3, coins = [2]
**输出：**0
**解释：**只用面额 2 的硬币不能凑成总金额 3 。

示例 3：
**输入：**amount = 10, coins = [10]
**输出：**1

提示：

• 1 <= coins.length <= 300
• 1 <= coins[i] <= 5000
• coins 中的所有值 互不相同
• 0 <= amount <= 5000

思路

---

完全背包问题。
设$dp[i][j]$为用前$i$种硬币凑成总金额$j$的组合数，得$dp[i][j]=dp[i-1][j]+dp[i-1][j-coins[i]]$滚动数组优化得$dp[j]=dp[j]+dp[j-coins[i]]$
初始化条件为$dp[0][0]=dp[0]=1$，$dp[0][1,amount]=dp[1,amount]=0$。
题目虽然说结果符合 32 位带符号整数，但是题目计算过程会超过范围，需要开unsigned long long才能通过。

答案

---

C++

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        unsigned long long dp[5010] = {1};
        for(int coin : coins)
            for(int j = coin; j <= amount; j++)
                dp[j] = dp[j] + dp[j - coin];
        return (int)dp[amount];
    }
};