跳转至

322. 零钱兑换（Coin Change）

频次 ★★★★★ · 难度 🟡 · 高频：字节/美团/阿里

题目

不同面额硬币 coins（无限供应），凑目标金额 amount 所需的最少硬币数，无法凑出返回 -1。

示例： 

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

思路

完全背包问题（DP）：dp[i] 表示凑 i 元的最少硬币数。

dp[i] = min(dp[i], dp[i - coin] + 1) for each coin ≤ i

初始化 dp[0] = 0，其余为 INF（amount + 1 即可）。

代码

public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);          // 上界（不可能达到）
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

dp[0] 设 0 还是设 1——按语义读，不按题背（本章第五考）

dp[0] = "目标 quantity=0 时的真实答案"——直接读出来即可。

题 dp 语义 dp[0] 理由
494/518/377 方案/组合/排列数 1 空方案也要被数到
416 判定 true 不选任何即凑出 0
322（本题） 最少枚数 0 0 元用 0 枚——枚数为 0
  • 计数流：dp[0]=1、+=、凑不出=0；最值流：dp[0]=0、min、凑不出=伪∞ → -1
  • 本题实际踩点：dp[0]=1（计数语义串门）→ 全表 +1（min 链底端污染）、amount=0 返 -1——语义倒推一行修正。
  • 伪 ∞ 用 amount+1 万不可 Integer.MAX_VALUE（+1 溢出）；贪心不成立（[1,3,4] 凑 6 → 贪 4+1+1=3 vs 真 3+3=2）

复杂度

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

边界条件

  • amount = 0：返回 0
  • 无解（如 [2], amount = 3）：dp[3] 保持 INF → 返回 -1
  • 大面额硬币超过 amount：不影响

变式

易错点

  • INF 初始化：amount + 1 是因为最多 amount 枚硬币（全部用 1 元），所以 amount+1 肯定不可达
  • 内层循环顺序：零钱兑换最少硬币数（完全背包求最值）对顺序不敏感，外面 for coin 或外面 for amount 都行。但如果是求组合数（518），外面 for coin 防重复计数
  • 返回前检查 dp[amount] > amount

面试追问

  • 为什么 518 换顺序就会重复计数？ 外层 for coin 保证"先选定面额再遍历金额"，每种组合只被计数一次（coin 的选取有顺序）。最少硬币数是最值，无所谓顺序

关联题