LeetCode零钱兑换（动态规划）

题目描述

给你一个整数数组 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, 2, 5]，目标是 120，问最少需要的硬币个数？

• 我们要分解子问题，分层级找最优子结构，看到这又要晕了哈，憋急~~ 下面马上举例。

• 这里我们使用「自顶向下」思想来考虑这个题目，然后用「自底向上」的方法来解题。

• dp是遍历金额总数构造的数组，dp[i]: 表示总金额为 i 的时候最优解法的硬币数，求dp[i]可以在dp中复用子问题解。

• 我们想一下：求总金额 120 有几种方法？下面这个思路关键了 !!!
  一共有 3 种方式，因为我们有 3 种不同面值的硬币。
  1.拿一枚面值为 1 的硬币 + 总金额为 119 的最优解法的硬币数量
  这里我们只需要假设总金额为 119 的最优解法的硬币数有人已经帮我们算好了，
  不需要纠结于此。(虽然一会也是我们自己算，哈哈)
  即：dp[119] + 1
  2.拿一枚面值为 2 的硬币 + 总金额为 118 的最优解法的硬币数
  这里我们只需要假设总金额为 118 的最优解法的硬币数有人已经帮我们算好了
  即：dp[118] + 1
  3.拿一枚面值为 5 的硬币 + 总金额为 115 的最优解法的硬币数
  这里我们只需要假设总金额为 115 的最优解法的硬币数有人已经帮我们算好了
  即：dp[115] + 1
  因为硬币的金额已知，所以dp[120]只能由这三种方法计算得到

  • 所以，总金额为 120 的最优解法就是上面这三种解法中最优的一种，也就是硬币数最少
    的一种，我们下面试着用代码来表示一下：

  • dp[120] = Math.min(dp[119] + 1, dp[118] + 1, dp[115] + 1);

  • 推导出「状态转移方程」：

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

其中 coin 有多少种可能，我们就需要比较多少次，那么我们到底需要比较多少次呢？ 当然是 coins 数组中有几种不同面值的硬币，就是多少次了~ 遍历 coins 数组， 分别去对比即可

• 上面方程中的 dp[119]，dp[118]，dp[115] 我们继续用这种思想去分解，
  这就是动态规划了，把这种思想，思考问题的方式理解了，这一类型的题目
  问题都不会太大。

代码

var coinChange = function(coins, amount) {let dp = new Array(amount + 1).fill(Infinity); // 初始化 dp 数组dp[0] = 0; // 凑出金额 0 所需的硬币数为 0for (let i = 1; i <= amount; i++) { // 遍历所有金额从 1 到 amountfor (let coin of coins) { // 遍历所有硬币面额if (i - coin >= 0) { // 如果当前金额 i 大于等于硬币面额 coindp[i] = Math.min(dp[i], dp[i - coin] + 1); // 更新 dp[i] 的值}}}return dp[amount] === Infinity ? -1 : dp[amount]; // 如果 dp[amount] 仍为 Infinity，说明无法凑出金额
};

代码分析

1. 初始化 dp 数组

let dp = new Array(amount + 1).fill(Infinity); // 初始化 dp 数组
dp[0] = 0; // 凑出金额 0 所需的硬币数为 0

• dp 数组的作用：dp[i] 表示凑出金额 i 所需的最少硬币数。
• 为什么用 Infinity 初始化：因为对于大多数金额，我们一开始不知道需要多少硬币才能凑出，所以用一个很大的数（Infinity）来表示“尚未计算”。
• dp[0] = 0：凑出金额 0 显然不需要任何硬币，所以 dp[0] 初始化为 0。

2. 外层循环：遍历所有金额

for (let i = 1; i <= amount; i++) { // 遍历所有金额从 1 到 amount

• 作用：我们需要计算从金额 1 到目标金额 amount 的每一个金额的最少硬币数。
• 逐步计算：从最小的金额开始，逐步向上计算，直到目标金额。这样可以确保在计算 dp[i] 时，所有小于 i 的金额的最少硬币数已经计算好了。

3. 内层循环：遍历所有硬币面额

for (let coin of coins) { // 遍历所有硬币面额

• 作用：对于每个金额 i，我们需要考虑所有可能的硬币面额，看看用哪种硬币可以更优地凑出金额 i。
• 逐个尝试：假设我们有硬币面额 [1, 2, 5]，对于金额 3，我们会尝试：
  • 用一枚面值为 1 的硬币，然后看 dp[2] 的值。
  • 用一枚面值为 2 的硬币，然后看 dp[1] 的值。
  • 用一枚面值为 5 的硬币，但 3 - 5 < 0，所以不能用。

4. 状态转移：更新 dp[i]

if (i - coin >= 0) { // 如果当前金额 i 大于等于硬币面额 coindp[i] = Math.min(dp[i], dp[i - coin] + 1); // 更新 dp[i] 的值
}

• 条件检查：if (i - coin >= 0) 确保我们不会用一个比当前金额还大的硬币，否则没有意义。
• 状态转移逻辑：
  • 假设我们正在计算金额 i，并且考虑用一枚面值为 coin 的硬币。
  • 如果我们用这枚硬币，那么剩下的金额就是 i - coin，凑出这个金额所需的硬币数是 dp[i - coin]。
  • 因为我们用了一枚硬币，所以总硬币数是 dp[i - coin] + 1。
  • 我们需要比较所有可能的硬币面额，选择最小的硬币数。这就是 Math.min(dp[i], dp[i - coin] + 1) 的作用。

5. 返回结果

return dp[amount] === Infinity ? -1 : dp[amount]; // 如果 dp[amount] 仍为 Infinity，说明无法凑出金额

• 检查结果：如果 dp[amount] 仍然是 Infinity，说明我们无法用给定的硬币面额凑出目标金额 amount，因此返回 -1。
• 返回最少硬币数：如果 dp[amount] 是一个有限的数，说明我们成功地找到了最少硬币数，直接返回它。

举例说明

假设 coins = [1, 2, 5]，amount = 11。

初始化

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

计算过程

1. 金额 i = 1：

   • 遍历硬币面额：
     • coin = 1：dp[1] = Math.min(Infinity, dp[0] + 1) = 1
   • 结果：dp = [0, 1, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity]

2. 金额 i = 2：

   • 遍历硬币面额：
     • coin = 1：dp[2] = Math.min(Infinity, dp[1] + 1) = 2
     • coin = 2：dp[2] = Math.min(2, dp[0] + 1) = 1
   • 结果：dp = [0, 1, 1, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity]

3. 金额 i = 3：

   • 遍历硬币面额：
     • coin = 1：dp[3] = Math.min(Infinity, dp[2] + 1) = 2
     • coin = 2：dp[3] = Math.min(2, dp[1] + 1) = 2
   • 结果：dp = [0, 1, 1, 2, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity]

4. 金额 i = 4：

   • 遍历硬币面额：
     • coin = 1：dp[4] = Math.min(Infinity, dp[3] + 1) = 3
     • coin = 2：dp[4] = Math.min(3, dp[2] + 1) = 2
   • 结果：dp = [0, 1, 1, 2, 2, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity]

5. 金额 i = 5：

   • 遍历硬币面额：
     • coin = 1：dp[5] = Math.min(Infinity, dp[4] + 1) = 3
     • coin = 2：dp[5] = Math.min(3, dp[3] + 1) = 3
     • coin = 5：dp[5] = Math.min(3, dp[0] + 1) = 1
   • 结果：dp = [0, 1, 1, 2, 2, 1, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity]

6. 金额 i = 6：

   • 遍历硬币面额：
     • coin = 1：dp[6] = Math.min(Infinity, dp[5] + 1) = 2
     • coin = 2：dp[6] = Math.min(2, dp[4] + 1) = 2
     • coin = 5：dp[6] = Math.min(2, dp[1] + 1) = 2
   • 结果：dp = [0, 1, 1, 2, 2, 1, 2, Infinity, Infinity, Infinity, Infinity, Infinity]

7. 金额 i = 7：

   • 遍历硬币面额：
     • coin = 1：dp[7] = Math.min(Infinity, dp[6] + 1) = 3
     • coin = 2：dp[7] = Math.min(3, dp[5] + 1) = 2
     • coin = 5：dp[7] = Math.min(2, dp[2] + 1) = 2
   • 结果：dp = [0, 1, 1, 2, 2, 1, 2, 2, Infinity, Infinity, Infinity, Infinity]

8. 金额 i = 8：

   • 遍历硬币面额：
     • coin = 1：dp[8] = Math.min(Infinity, dp[7] + 1) = 3
     • coin = 2：dp[8] = Math.min(3, dp[6] + 1) = 3
     • coin = 5：dp[8] = Math.min(3, dp[3] + 1) = 3
   • 结果：dp = [0, 1, 1, 2, 2, 1, 2, 2, 3, Infinity, Infinity, Infinity]

9. 金额 i = 9：

   • 遍历硬币面额：
     • coin = 1：dp[9] = Math.min(Infinity, dp[8] + 1) = 4
     • coin = 2：dp[9] = Math.min(4, dp[7] + 1) = 3
     • coin = 5：dp[9] = Math.min(3, dp[4] + 1) = 3
   • 结果：dp = [0, 1, 1, 2, 2, 1, 2, 2, 3, 3, Infinity, Infinity]

10. 金额 i = 10：

    • 遍历硬币面额：
      • coin = 1：dp[10] = Math.min(Infinity, dp[9] + 1) = 4
      • coin = 2：dp[10] = Math.min(4, dp[8] + 1) = 4
      • coin = 5：dp[10] = Math.min(4, dp[5] + 1) = 2
    • 结果：dp = [0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, Infinity]

11. 金额 i = 11：

    • 遍历硬币面额：
      • coin = 1：dp[11] = Math.min(Infinity, dp[10] + 1) = 3
      • coin = 2：dp[11] = Math.min(3, dp[9] + 1) = 3
      • coin = 5：dp[11] = Math.min(3, dp[6] + 1) = 3
    • 结果：dp = [0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3]

最终结果

• dp[11] = 3，表示凑出金额 11 所需的最少硬币数为 3。

总结

这段代码通过动态规划的思想，逐步计算出每个金额的最少硬币数，最终得到目标金额的最少硬币数。