#322.零钱兑换

LeetCode 原题链接

#1.dp 数组含义

定义一维数组 dp：

dp[j] 表示凑成金额 j 所需要的最少硬币数量。

题目要求凑成 amount 的最少硬币数，所以最终答案就是：

dp[amount]

如果某个金额无法被凑出来，就让它保持为一个很大的值，最后再判断是否需要返回 -1。

#2. 确定状态转移方程

假设当前有一枚硬币 coin，现在要计算金额 j 的最少硬币数。

如果选择使用这枚硬币，那么在使用它之前，需要先凑出金额：

j - coin

如果 j - coin 可以凑出来，那么再加上当前这 1 枚硬币，就可以凑出 j：

dp[j - coin] + 1

但是 dp[j] 可能之前已经通过其他硬币组合得到过更小值，所以要取最小值：

dp[j] = Math.min(dp[j], dp[j - coin] + 1);

一句话总结：凑成金额 j 的最后一步，可以是先凑成 j - coin，再放入一枚面值为 coin 的硬币。

#3.dp 数组如何初始化

dp[0] = 0：

凑成金额 0 不需要任何硬币，所以最少硬币数是 0。

其他位置初始化为 Infinity：

dp[j] = Infinity;

原因是：一开始还不知道这些金额能不能被凑出来，用 Infinity 表示“暂时无法凑成”。

后续转移时，如果某个金额可以被凑出来，就会被更新成更小的硬币数量。

例如：

const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0;

数组长度是 amount + 1，因为下标要从 0 一直到 amount，每个下标都表示一个具体金额。

#4. 确定遍历顺序

这道题每种硬币可以使用无限次，所以是完全背包问题。

可以先遍历硬币，再正序遍历金额：

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

#详细解释内循环

固定当前硬币 coin 后，内循环会依次计算：加入这枚硬币后，凑成金额 j 最少需要多少枚硬币。

for (let j = coin; j <= amount; j++) {
  dp[j] = Math.min(dp[j], dp[j - coin] + 1);
}

#j 表示当前要凑出的金额

j 不是硬币数量，而是当前正在计算的目标金额。

例如 coin = 2、amount = 5 时，内循环中的 j 会依次取：

2、3、4、5

也就是依次判断：使用硬币 2 后，能否让 dp[2]、dp[3]、dp[4]、dp[5] 变得更小。

#为什么从j = coin 开始

当目标金额小于当前硬币面值时，无法放入这枚硬币。

例如当前硬币是 5：

金额 0、1、2、3、4 都无法放入硬币 5

因此不需要检查这些金额，直接从 j = coin 开始。这样还能保证 j - coin >= 0，访问 dp[j - coin] 时不会越界。

#状态转移语句的两种选择

dp[j] = Math.min(dp[j], dp[j - coin] + 1);

这行代码是在比较两种选择：

1. 不使用当前这枚硬币：保留原来的 dp[j]。
2. 使用一枚当前硬币：先用最少的硬币凑出 j - coin，再加上一枚面值为 coin 的硬币，硬币数为 dp[j - coin] + 1。

例如当前 coin = 2，正在计算 j = 5：

dp[5] = Math.min(dp[5], dp[3] + 1);

其中：

• dp[5] 表示不使用当前硬币 2 时，之前已经得到的最优结果。
• dp[3] + 1 表示先凑成金额 3，再加入一枚硬币 2，从而凑成金额 5。

如果 dp[3] 仍然是 Infinity，说明金额 3 无法凑出：

Infinity + 1 === Infinity;

此时 dp[5] 不会被这个无效方案更新。

#为什么j 必须正序遍历

内循环正序遍历时，较小金额的状态会先被更新，后面的较大金额可以继续使用这个新状态，因此同一种硬币可以使用多次。

假设开始时：

dp = [0, Infinity, Infinity, Infinity, Infinity]
coin = 2

内循环的更新过程如下：

j = 2：dp[2] = min(Infinity, dp[0] + 1) = 1
       得到方案 2

j = 3：dp[3] = min(Infinity, dp[1] + 1) = Infinity
       金额 3 仍然无法凑出

j = 4：dp[4] = min(Infinity, dp[2] + 1) = 2
       此时使用的是本轮刚更新的 dp[2]，得到方案 2 + 2

计算 dp[4] 时使用了当前硬币这一轮刚更新的 dp[2]，所以硬币 2 被使用了两次。这就是完全背包中金额需要正序遍历的原因。

如果改成倒序遍历，计算 dp[4] 时看到的 dp[2] 还是上一轮的旧值，同一轮中当前硬币只能被使用一次，就变成了 0-1 背包的处理方式。

#5. 举例打印dp 数组

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

初始化：

#使用硬币1

硬币 1 可以凑出所有金额：

例如：

dp[3] = dp[2] + 1 = 3

表示凑成金额 3 最少需要 3 枚 1。

#使用硬币2

加入硬币 2 后，很多金额可以用更少硬币凑出来：

例如：

dp[4] = Math.min(4, dp[2] + 1) = 2

表示金额 4 可以用 2 + 2 凑出来，只需要 2 枚硬币。

#使用硬币5

继续加入硬币 5：

例如：

dp[11] = Math.min(6, dp[6] + 1) = 3

此时 dp[6] = 2，表示金额 6 可以用 5 + 1 或 2 + 2 + 2 中更优的方式凑出来，再加一枚 5，金额 11 最少需要 3 枚硬币。

最终：

dp[11] = 3

对应一种方案：

11 = 5 + 5 + 1

所以返回 3。

#6. 代码实现

var coinChange = function (coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;

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

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

#复杂度分析

• 时间复杂度：O(coins.length * amount)，需要枚举每枚硬币和每个金额。
• 空间复杂度：O(amount)，只需要一个一维 dp 数组。