跳到主要内容

零钱兑换

问题​

给你一个整数数组 coins（表示不同面额的硬币）和一个整数 amount（总金额），计算凑成总金额所需的最少硬币数。如果无法凑成，返回 -1。每种硬币的数量是无限的。

示例：

输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1

来源：LeetCode 322. 零钱兑换

经典问题

零钱兑换是「完全背包」问题的变体，也是面试中最常考的 DP 题之一。

答案​

方法一：动态规划（自底向上，推荐）​

状态定义：dp[i] = 凑成金额 i 所需的最少硬币数。

转移方程：

dp[i]=min⁡coin∈coins(dp[i−coin]+1)dp[i] = \min_{coin \in coins}(dp[i - coin] + 1)
coinChange.ts
function coinChange(coins: number[], amount: number): number {
  // dp[i] = 凑成金额 i 的最少硬币数
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0; // 金额 0 不需要硬币

  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (coin <= i && dp[i - coin] !== Infinity) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }

  return dp[amount] === Infinity ? -1 : dp[amount];
}

图解（coins = [1, 2, 5], amount = 11）：

i:    0  1  2  3  4  5  6  7  8  9  10  11
dp:   0  1  1  2  2  1  2  2  3  3   2   3

dp[1] = dp[0]+1 = 1         (用硬币 1)
dp[2] = min(dp[1]+1, dp[0]+1) = 1  (用硬币 2)
dp[5] = min(dp[4]+1, dp[3]+1, dp[0]+1) = 1  (用硬币 5)
dp[11] = min(dp[10]+1, dp[9]+1, dp[6]+1) = min(3,4,3) = 3
复杂度分析
  • 时间复杂度：O(amount×n)O(amount \times n) — n 为硬币种类
  • 空间复杂度：O(amount)O(amount) — dp 数组

方法二：记忆化递归（自顶向下）​

coinChangeMemo.ts
function coinChange(coins: number[], amount: number): number {
  const memo = new Map<number, number>();

  function dp(remaining: number): number {
    if (remaining === 0) return 0;
    if (remaining < 0) return -1;
    if (memo.has(remaining)) return memo.get(remaining)!;

    let minCoins = Infinity;
    for (const coin of coins) {
      const sub = dp(remaining - coin);
      if (sub !== -1) {
        minCoins = Math.min(minCoins, sub + 1);
      }
    }

    const result = minCoins === Infinity ? -1 : minCoins;
    memo.set(remaining, result);
    return result;
  }

  return dp(amount);
}

方法三：BFS（图论思维）​

把每个金额看作一个节点，每种硬币代表一条边：

coinChangeBFS.ts
function coinChange(coins: number[], amount: number): number {
  if (amount === 0) return 0;

  const visited = new Set<number>();
  const queue: number[] = [0];
  visited.add(0);
  let steps = 0;

  while (queue.length > 0) {
    steps++;
    const size = queue.length;

    for (let i = 0; i < size; i++) {
      const current = queue.shift()!;

      for (const coin of coins) {
        const next = current + coin;
        if (next === amount) return steps;
        if (next < amount && !visited.has(next)) {
          visited.add(next);
          queue.push(next);
        }
      }
    }
  }

  return -1;
}
BFS 为什么能求最短路？

BFS 的特性：第一次到达目标节点时，经过的层数就是最短路径。 每一层代表"多用了一个硬币"，所以第一次到达 amount 时，硬币数最少。

常见面试追问​

Q1: 零钱兑换 II——有多少种组合方式？(LeetCode 518)​

答案：注意是组合（不分顺序），外层遍历硬币，内层遍历金额：

function change(amount: number, coins: number[]): number {
  const dp = new Array(amount + 1).fill(0);
  dp[0] = 1; // 凑成 0 元有 1 种方式（什么都不选）

  for (const coin of coins) {       // 外层遍历硬币 → 保证组合
    for (let i = coin; i <= amount; i++) {
      dp[i] += dp[i - coin];
    }
  }

  return dp[amount];
}
组合 vs 排列
  • 外层硬币，内层金额 → 组合（[1,2] 和 [2,1] 算同一种）
  • 外层金额，内层硬币 → 排列（[1,2] 和 [2,1] 算两种）

Q2: 贪心可以吗？​

答案：直觉上"总是选最大面额"似乎可行，但贪心不一定正确。

反例：coins = [1, 3, 4], amount = 6

  • 贪心：4 + 1 + 1 = 3 枚
  • 最优：3 + 3 = 2 枚

只有特定硬币系统（如人民币体系）贪心才正确。

Q3: 这道题和「爬楼梯」的关系？​

答案：本质相同！都是「完全背包」问题：

  • 爬楼梯：步幅 [1,2]，到 n 阶的方案数
  • 零钱兑换：硬币面额，凑 amount 的方案数/最少个数

区别在于爬楼梯求的是排列数（1+2 和 2+1 不同），零钱兑换求最少个数或组合数。

相关链接​