518. 零钱兑换 II
题目描述
输入整数 amount 表示要凑出的总金额，数组 coins 列出各种硬币的面额，每种面额的硬币可以使用任意多枚。
统计有多少种不同的硬币组合，其面额之和恰好等于 amount。组合只看每种面额各用几枚，不看先后顺序，所以 1+2 和 2+1 算同一种。
返回组合的个数；一种都凑不出来时返回 0。题目保证答案在 32 位有符号整数范围内。
示例 1
输入：amount = 5, coins = [1,2,5] 输出：4
解释：四种组合：5、2+2+1、2+1+1+1、1+1+1+1+1。
示例 2
输入：amount = 3, coins = [2] 输出：0
解释：只有面额 2，凑不出奇数 3。
示例 3
输入：amount = 10, coins = [10] 输出：1
解释：一枚 10 正好凑出 10。
数据范围
1 <= coins.length <= 3001 <= coins[i] <= 5000coins中的面额互不相同。0 <= amount <= 5000
解题思路
完全背包计数。dp[x] 表示用“已处理过的硬币”凑出 x 的组合数，dp[0] = 1。外层遍历硬币，内层 x 从 c 到 amount 从小到大：dp[x] += dp[x - c]。外层是硬币，意味着每个组合都按硬币顺序唯一生成，不会把不同排列重复计入；内层正序让 dp[x-c] 已包含当前硬币，从而同一硬币可以重复使用。
为什么正确
处理完前 k 种硬币后，dp[x] 等于只用这 k 种硬币（各任意个）凑出 x 的组合数。
复杂度分析
时间 O(len(coins) · amount)，空间 O(amount)。
易错点
把两层循环交换（外层金额、内层硬币）算的是排列数，会把 1+2 和 2+1 算两次。内层若倒序遍历则变成每种硬币最多用一次（0-1 背包）。dp[0] = 1 不能写成 0。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp = [0] * (amount + 1)
dp[0] = 1
for c in coins:
for x in range(c, amount + 1):
dp[x] += dp[x - c]
return dp[amount]class Solution {
public int change(int amount, int[] coins) {
long[] dp = new long[amount + 1];
dp[0] = 1;
for (int c : coins) {
for (int x = c; x <= amount; x++) {
dp[x] += dp[x - c];
}
}
return (int) dp[amount];
}
}class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<unsigned long long> dp(amount + 1, 0);
dp[0] = 1;
for (int c : coins) {
for (int x = c; x <= amount; x++) {
dp[x] += dp[x - c];
}
}
return (int)dp[amount];
}
};func change(amount int, coins []int) int {
dp := make([]uint64, amount+1)
dp[0] = 1
for _, c := range coins {
for x := c; x <= amount; x++ {
dp[x] += dp[x-c]
}
}
return int(dp[amount])
}var change = function(amount, coins) {
const dp = new Array(amount + 1).fill(0);
dp[0] = 1;
for (const c of coins) {
for (let x = c; x <= amount; x++) {
dp[x] += dp[x - c];
}
}
return dp[amount];
};function change(amount: number, coins: number[]): number {
const dp = new Array(amount + 1).fill(0);
dp[0] = 1;
for (const c of coins) {
for (let x = c; x <= amount; x++) {
dp[x] += dp[x - c];
}
}
return dp[amount];
}