#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);
  }
}

金额 j 必须正序遍历，因为 dp[j] 会依赖当前这一轮已经更新过的 dp[j - coin]。

这正好表示：同一种硬币可以被重复使用。

例如当前硬币是 2：

dp[4] 可以由 dp[2] + 1 转移而来。

如果 dp[2] 已经在当前硬币 2 这一轮被更新过，那么 dp[4] 就可以继续使用第二枚 2。

#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 数组。