跳转至

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

为什么"和自己加"——集合记账实测（c=2 轮的 dp[3] 格）

处理面额 2 前：dp[3]={1,1,1}（旧世界躺着的集合）
面额 2 入场，凑 3 的搭配按"用不用 2"一刀两分：
  ① 不用 2：{1,1,1}          ← 恰好 = dp[3] 的旧值本身（新面额从不作废旧可能）
  ② 用 2：  {1,2}            ← 拆一枚 2 → dp[1] 的世界补一枚
⟹ dp[j] = dp[j]（①保留） + dp[j−c]（②原料）  += 即"旧值留着再累加"
  • 反例核：写成替换 dp[j]=dp[j−c] → {1,1,1} 被丢、凑5 全错——"新面额只增可能不清可能"
  • 正序读 dp[j−c] 是"本轮刚写过"= 已含新面额的世界（允许无限用）；倒序读的是旧世界（01 只用一次）——内外层方向语义全在此
  • 外层=物品 → 组合数；外层=容量 → 排列数（377 对照）
  • 同族钩：416 ||= / 494 += / 518 += ——"旧值=合法过去，新值=合法新增，互斥相加不重不漏"

复杂度

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

边界条件

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

变式

易错点

  • 内外层顺序决定组合 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

关联题