跳至主要內容

LeetCode 322. 零钱兑换

Skyme2026/8/20大约 7 分钟刷题Hot 100动态规划记忆化搜索数组

LeetCode 322. 零钱兑换

题目核心

给你一个整数数组 coins，表示不同面额的硬币；以及一个整数 amount，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

例如：

coins = [1, 2, 5], amount = 11
返回 3（11 = 5 + 5 + 1）

coins = [2], amount = 3
返回 -1（无法凑出 3）

coins = [1], amount = 0
返回 0（金额为 0，不需要硬币）

解题思考过程

第一步：理解问题

这是一个典型的"完全背包"变种问题：每种硬币可以无限使用，求凑出目标金额的最少硬币数。

本质上是在问：从 coins 中反复选硬币（可以重复选），能不能刚好凑出 amount？如果能，最少用几枚？

第二步：暴力递归

最直接的思路：对于当前金额 amount，尝试选每一种硬币：

dfs(amount):
  if amount == 0: return 0
  res = 无穷大
  for coin in coins:
    if amount >= coin:
      res = min(res, dfs(amount - coin) + 1)
  return res

但这个方法有大量重复计算：

dfs(11) 需要 dfs(10), dfs(9), dfs(6)
dfs(10) 需要 dfs(9), dfs(8), dfs(5)
dfs(9) 被算了两次...

时间复杂度：O(k^n)（k 是硬币种类），指数级，完全无法通过。

第三步：记忆化优化

观察到：dfs(amount) 的结果只取决于 amount，跟之前选了什么硬币无关。

所以可以用一个 mem 数组把每个金额的结果存下来，下次再遇到直接返回。

  • mem[amount] == -1（或其他特殊值）：还没算过。
  • mem[amount] 已经有值：直接返回。

加上记忆化后，每个金额只计算一次，时间复杂度降为 O(amount * k)。

第四步：动态规划

记忆化搜索是自顶向下的，也可以改成自底向上的动态规划：

dp[i] 表示凑出金额 i 所需的最少硬币数

dp[0] = 0
dp[i] = min(dp[i - coin] + 1)  对所有 coin <= i

初始化时把 dp 数组填成一个不可能的大数（比如 amount + 1），表示"暂时凑不出来"。最后如果 dp[amount] 还是大于 amount，说明凑不出来，返回 -1。

当前代码需要改进的地方

用户提供的代码已经写出了正确的"选硬币"递归关系，也创建了 mem 数组，但还有几个细节问题需要修正。

问题一：mem 初始值与返回值冲突

const mem = new Array(amount + 1).fill(-1);

这里用 -1 表示"还没算过"，但题目最终凑不出来时也要返回 -1。如果某个金额真的凑不出来，mem[amount] 存的是 1000000000，虽然不冲突，但语义不清晰。更好的做法是用两个不同的哨兵值，或者用 Infinity 存"凑不出来"。

问题二：递归参数名拼写错误

const dfs = (conins, amount) => {

参数名写成了 conins，但函数体里用的是 coins。虽然因为闭包能拿到外层的 coins 不会报错，但这是一个明显的拼写 bug。

问题三：大数的选择不够严谨

let num = 1000000000;

硬币最多不会超过 amount 枚（全用 1 元硬币）。用 amount + 1 作为"不可能"的上限更合理，也更不容易溢出。

问题四：amount 为 0 时，mem 没有存入结果

amount === 0 时直接 return 0，但没有把 0 存入 mem[0]。虽然不会出错，但一致性不好。

下面是修正后的完整解法。

解法一：记忆化搜索（DFS + Memo）

在普通递归的基础上，用 mem[amt] 保存凑出金额 amt 所需的最少硬币数。再次遇到相同金额直接返回。

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function (coins, amount) {
  const UNCALC = -1;
  const IMPOSSIBLE = amount + 1;
  const mem = new Array(amount + 1).fill(UNCALC);

  const dfs = (amt) => {
    if (amt === 0) return 0;
    if (mem[amt] !== UNCALC) return mem[amt];

    let minCount = IMPOSSIBLE;
    for (const coin of coins) {
      if (amt >= coin) {
        minCount = Math.min(minCount, dfs(amt - coin) + 1);
      }
    }

    mem[amt] = minCount;
    return minCount;
  };

  const res = dfs(amount);
  return res >= IMPOSSIBLE ? -1 : res;
};

代码逐行解释

准备工作

const UNCALC = -1;
const IMPOSSIBLE = amount + 1;
const mem = new Array(amount + 1).fill(UNCALC);
  • UNCALC = -1：表示这个金额还没计算过。
  • IMPOSSIBLE = amount + 1：表示这个金额凑不出来。因为最坏情况全用 1 元硬币也只需要 amount 枚，所以 amount + 1 一定是不可能的上限。
  • mem：长度 amount + 1，记录每个金额的最少硬币数。

dfs 函数

const dfs = (amt) => {
  if (amt === 0) return 0;

递归终点：金额为 0 时，不需要任何硬币，返回 0。

if (mem[amt] !== UNCALC) return mem[amt];

记忆化查询：如果这个金额之前算过，直接返回记录的结果。

let minCount = IMPOSSIBLE;
for (const coin of coins) {
  if (amt >= coin) {
    minCount = Math.min(minCount, dfs(amt - coin) + 1);
  }
}

核心逻辑：尝试选每一种硬币。如果硬币面额不超过当前金额，就选这枚硬币（+1），然后递归解决剩下的金额 amt - coin。在所有选择中取硬币数最少的那个。

  mem[amt] = minCount;
  return minCount;
};

保存结果：无论能不能凑出来，都把结果存入 mem[amt]，下次遇到直接用。

最终判断

const res = dfs(amount);
return res >= IMPOSSIBLE ? -1 : res;

如果最终结果还是 IMPOSSIBLE（或更大），说明凑不出来，返回 -1；否则返回最少硬币数。

执行过程示例

以 coins = [1, 2, 5], amount = 11 为例：

dfs(11):
  选 1 → dfs(10) + 1
  选 2 → dfs(9)  + 1
  选 5 → dfs(6)  + 1
  取三者最小

dfs(6):
  选 1 → dfs(5) + 1
  选 2 → dfs(4) + 1
  选 5 → dfs(1) + 1
  ...

dfs(5):
  选 5 → dfs(0) + 1 = 1  ← 直接命中终点
  ...

最终：
dfs(5)  = 1 （5）
dfs(6)  = 2 （5 + 1）
dfs(11) = 3 （5 + 5 + 1）

答案是 3。

再看一个失败的例子：coins = [2], amount = 3

dfs(3):
  选 2 → dfs(1) + 1
    dfs(1):
      2 > 1，不能选，minCount 保持 IMPOSSIBLE
      mem[1] = IMPOSSIBLE
  minCount = IMPOSSIBLE
  mem[3] = IMPOSSIBLE

返回 -1

为什么不用 0 初始化 mem

因为最少硬币数本身就可能是 0（当 amount 为 0 时）。如果用 0 表示"还没算过"，就无法区分"没算过"和"答案是 0"两种情况，所以用 -1 作为未计算的标记。

复杂度

  • 时间复杂度：O(amount * k)，其中 k 是硬币种类数。每个金额状态只会被真正计算一次，每次计算遍历 k 种硬币。
  • 空间复杂度：O(amount)。mem 数组长度 amount + 1，递归栈深度最多也是 amount。

解法二：动态规划

记忆化搜索是自顶向下递归，也可以改成自底向上迭代。从金额 0 开始，一步步推到 amount。

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function (coins, amount) {
  const IMPOSSIBLE = amount + 1;
  const dp = new Array(amount + 1).fill(IMPOSSIBLE);
  dp[0] = 0;

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

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

状态定义

dp[i]：凑出金额 i 所需的最少硬币数

初始化

dp[0] = 0;

金额 0 不需要硬币，这是整个递推的起点。

状态转移

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

从 1 到 amount，对每个金额 i：

  • 尝试选每一种硬币 coin。
  • 如果 coin <= i，说明可以选这枚硬币：凑出 i - coin 的最少硬币数 +1，就是选 coin 时的答案。
  • 在所有硬币中取最小值。

最终判断

return dp[amount] >= IMPOSSIBLE ? -1 : dp[amount];

和记忆化搜索一样，如果 dp[amount] 没有被更新为一个合理的值，说明凑不出来，返回 -1。

执行示例

coins = [1, 2, 5], amount = 11：

dp[0] = 0

dp[1]:
  选 1 → dp[0] + 1 = 1
  dp[1] = 1

dp[2]:
  选 1 → dp[1] + 1 = 2
  选 2 → dp[0] + 1 = 1  ← 更小
  dp[2] = 1

dp[3]:
  选 1 → dp[2] + 1 = 2
  选 2 → dp[1] + 1 = 2
  dp[3] = 2

dp[5]:
  选 1 → dp[4] + 1
  选 2 → dp[3] + 1 = 3
  选 5 → dp[0] + 1 = 1  ← 最小
  dp[5] = 1

...

dp[11]:
  选 1 → dp[10] + 1 = 3
  选 2 → dp[9]  + 1 = 4
  选 5 → dp[6]  + 1 = 3  ← 最小
  dp[11] = 3

最终 dp[11] = 3。

两种解法对比

解法时间复杂度空间复杂度特点
记忆化搜索O(amount * k)O(amount)贴近"选硬币"的直觉思考过程，写法自然
动态规划O(amount * k)O(amount)迭代写法，无递归栈开销，适合最终提交

两种解法本质相同：都是对每个金额，枚举选哪枚硬币，取最少硬币数。

第一次理解这道题时，建议先写记忆化搜索，想清楚 dfs(amt) 的含义和"选硬币"的递归关系后，再改写动态规划会轻松很多。

路的尽头依旧是路
Copyright © 2026 Skyme