518. 零钱兑换 II（Coin Change II）

频次 ★★★★ · 难度 🟡 · 高频：字节/腾讯/美团

题目

不同面额硬币 coins（无限供应），凑目标金额 amount 的组合数（不关心顺序）。与 322 题的区别：322 求最少硬币数，本题求方案数。

示例：

输入: amount = 5, coins = [1,2,5]
输出: 4  （5=5, 5=2+2+1, 5=2+1+1+1, 5=1+1+1+1+1）

思路

完全背包求组合数：dp[j] 表示凑金额 j 的组合数。

dp[j] += dp[j - coin]，初始化 dp[0] = 1。

关键：外层遍历硬币，内层遍历金额（正序）。这样保证”组合数”——每种硬币的选取顺序固定，不会因为顺序不同产生重复计数（如 {1,2} 和 {2,1} 算同一种）。

代码

public int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    dp[0] = 1;                               // 凑 0 元有一种方式（不选任何硬币）
    for (int coin : coins) {                  // 外层：硬币（保证组合数）
        for (int j = coin; j <= amount; j++) { // 内层：金额（正序 = 完全背包）
            dp[j] += dp[j - coin];
        }
    }
    return dp[amount];
}

复杂度

• 时间：O(n × amount)，n = 硬币种类数
• 空间：O(amount)

边界条件

• amount = 0：返回 1（空组合）
• 无解（如 coins=[2], amount=3）：dp[amount] 保持 0

变式

• 377. 组合总和 IV：求排列数——内外层交换
• 322. 零钱兑换：求最少硬币数——完全背包求最值，内外层循环顺序无关
• 39. 组合总和：求所有具体组合（回溯），本题只求计数

易错点

• 内外层顺序决定组合 vs 排列：外层硬币 = 组合（coin 顺序固定），外层金额 = 排列（不同顺序算不同方案）
• 内层正序（完全背包可重复选），不是逆序（0-1 背包）
• 内层 for (int j = coin; j <= amount; j++) 从 coin 起步，j < coin 时 dp[j-coin] 越界且无意义
• dp[0] = 1 是计数 DP 的基值（空集算一种组合），不是真实含义
• 这道题和 377 的唯一区别就是内外层顺序——面试中常对比问

面试追问

• 为什么外层硬币保证组合数？ 硬币在外层时，遍历顺序固定为先处理 coin1 的所有金额，再处理 coin2……这样每种组合只被计算一次
• 如果要求排列数（顺序不同算不同）？ 内外层交换：外层金额，内层硬币 → 377 题
• 要返回具体组合而不是计数怎么办？ 改用回溯搜索（DFS）逐个构造，见 39 题；但 amount 大时组合数爆炸，只能计数
• 硬币面额是小数怎么办？ dp 数组不能按金额索引，把金额统一乘 10ᵏ 转成整数再 DP，或者改用哈希表做稀疏 DP

关联题

• 同套路：377. 组合总和 IV —— 排列数（内外层交换）
• 同套路：416. 分割等和子集 —— 0-1 背包（每个物品最多用一次）
• 基础：322. 零钱兑换 —— 最少硬币数
• 进阶：39. 组合总和 —— 回溯求出所有具体组合
• 知识点：完全背包（组合 vs 排列）见动态规划