算法刷题 322. 零钱兑换

322. 零钱兑换

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

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

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

示例 1：

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

示例 2：

输入：coins = [2], amount = 3
输出：-1
示例 3：

输入：coins = [1], amount = 0
输出：0

提示：

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

这段代码实现了一个函数 coinChange，用于计算用给定的硬币数组 coins 兑换指定金额 amount 所需的最少硬币数量。如果无法兑换，则返回 -1。

以下是代码的详细解释和注释：

var coinChange = function (coins, amount) {
    // 创建一个长度为 amount + 1 的数组 dp，并初始化为 Infinity
    let dp = new Array(amount + 1).fill(Infinity);
    // 初始化 dp[0] 为 0，因为面额 0 只需要 0 个硬币
    dp[0] = 0;

    // 遍历从 1 到 amount 的每一个金额 i
    for (let i = 1; i <= amount; i++) {
        // 遍历每一个硬币 coin
        for (let coin of coins) {
            // 如果当前金额 i 大于等于硬币的面值 coin
            if (i - coin >= 0) {
                // 更新 dp[i]，选择最小的硬币数量
                // dp[i - coin] 表示当前金额 i 减去当前硬币面值所需的最少硬币数量
                // dp[i] 可由 dp[i - coin] + 1 转换而来
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    // 如果 dp[amount] 仍然是 Infinity，表示无法兑换，返回 -1
    // 否则返回 dp[amount]，即兑换 amount 所需的最少硬币数量
    return dp[amount] === Infinity ? -1 : dp[amount];
};

详细解释

1. 初始化动态规划数组 dp:

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

   创建一个长度为 amount + 1 的数组 dp，并将所有元素初始化为 Infinity。dp[i] 表示兑换金额 i 所需的最少硬币数量。初始化 dp[0] 为 0，因为面额 0 只需要 0 个硬币。

2. 遍历从 1 到 amount 的每一个金额 i:

   for (let i = 1; i <= amount; i++) {
   

   对于每个金额 i，尝试计算兑换该金额所需的最少硬币数量。

3. 遍历每一个硬币 coin:

   for (let coin of coins) {
   

   对于每个硬币 coin，检查是否可以用该硬币兑换当前金额 i。

4. 更新 dp[i]:

   if (i - coin >= 0) {
       dp[i] = Math.min(dp[i], dp[i - coin] + 1);
   }
   

   如果当前金额 i 大于等于硬币的面值 coin，则更新 dp[i] 为 dp[i - coin] + 1 的最小值。dp[i - coin] 表示当前金额 i 减去当前硬币面值所需的最少硬币数量，加上当前硬币的数量 1。

5. 返回结果:

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

   最后，如果 dp[amount] 仍然是 Infinity，表示无法兑换，返回 -1。否则返回 dp[amount]，即兑换 amount 所需的最少硬币数量。

示例

假设 coins = [1, 2, 5]，amount = 11，代码的执行过程如下：

• i = 1，dp[1] = 1（1 = 1）
• i = 2，dp[2] = 1（2 = 2）
• i = 3，dp[3] = 2（3 = 2 + 1）
• i = 4，dp[4] = 2（4 = 2 + 2）
• i = 5，dp[5] = 1（5 = 5）
• i = 6，dp[6] = 2（6 = 5 + 1）
• i = 7，dp[7] = 2（7 = 5 + 2）
• i = 8，dp[8] = 3（8 = 5 + 2 + 1）
• i = 9，dp[9] = 3（9 = 5 + 2 + 2）
• i = 10，dp[10] = 2（10 = 5 + 5）
• i = 11，dp[11] = 3（11 = 5 + 5 + 1）

最终，dp[11] 的值为 3，表示 11 可以由 3 个硬币组成（5 + 5 + 1）。

let dp = new Array(amount + 1).fill(Infinity);为什么要 amount+1

在动态规划问题中，数组 dp 通常用于存储从 0 到目标值（在这个例子中是 amount）的每个子问题的解。为了能够存储从 0 到 amount 的所有值，我们需要一个长度为 amount + 1 的数组。

详细解释

假设 amount 为 5，那么我们需要一个数组 dp 来存储从 0 到 5 的每个金额所需的最少硬币数量。数组的索引表示金额，数组的值表示兑换该金额所需的最少硬币数量。

• dp[0] 表示兑换金额 0 所需的最少硬币数量。
• dp[1] 表示兑换金额 1 所需的最少硬币数量。
• dp[2] 表示兑换金额 2 所需的最少硬币数量。
• dp[3] 表示兑换金额 3 所需的最少硬币数量。
• dp[4] 表示兑换金额 4 所需的最少硬币数量。
• dp[5] 表示兑换金额 5 所需的最少硬币数量。

为了能够存储这些值，数组 dp 的长度需要是 amount + 1，即 6。

代码示例

let dp = new Array(amount + 1).fill(Infinity);

• new Array(amount + 1) 创建一个长度为 amount + 1 的数组。
• .fill(Infinity) 将数组的每个元素初始化为 Infinity，表示初始状态下无法兑换这些金额。

为什么需要 amount + 1

1. 索引从 0 开始:
   JavaScript 数组的索引从 0 开始。如果我们只创建一个长度为 amount 的数组，那么我们只能存储从 0 到 amount - 1 的值，而无法存储 amount 本身的值。

2. 包含所有子问题:
   动态规划的核心思想是通过解决子问题来解决原问题。为了能够解决 amount 的问题，我们需要解决从 0 到 amount 的所有子问题。因此，数组的长度需要是 amount + 1。

示例

假设 amount = 5，我们需要一个长度为 6 的数组 dp：

let dp = new Array(6).fill(Infinity);

初始化后，dp 数组如下：

dp = [Infinity, Infinity, Infinity, Infinity, Infinity, Infinity]

然后我们设置 dp[0] = 0，因为兑换金额 0 只需要 0 个硬币：

dp[0] = 0;

此时，dp 数组如下：

dp = [0, Infinity, Infinity, Infinity, Infinity, Infinity]

接下来，我们通过动态规划填充 dp 数组，最终得到兑换 amount 所需的最少硬币数量。

总结

使用 amount + 1 的数组长度是为了确保我们能够存储从 0 到 amount 的所有子问题的解，从而能够正确地解决整个问题。