算法刷题 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

1 // 遍历每一个硬币 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]; }; 详细解释

初始化动态规划数组 dp:

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

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

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

更新 dp[i]:

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

返回结果:

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

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

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

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

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

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

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

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

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

初始化后，dp 数组如下：

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

此时，dp 数组如下：

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

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