本文主要是介绍算法刷题 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，并初始化为 Infinitylet dp = new Array(amount + 1).fill(Infinity);// 初始化 dp[0] 为 0，因为面额 0 只需要 0 个硬币dp[0] = 0;// 遍历从 1 到 amount 的每一个金额 ifor (let i = 1; i <= amount; i++) {// 遍历每一个硬币 coinfor (let coin of coins) {// 如果当前金额 i 大于等于硬币的面值 coinif (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:let dp = new Array(amount + 1).fill(Infinity); dp[0] = 0;创建一个长度为
amount + 1的数组dp，并将所有元素初始化为Infinity。dp[i]表示兑换金额i所需的最少硬币数量。初始化dp[0]为 0，因为面额 0 只需要 0 个硬币。 -
遍历从 1 到 amount 的每一个金额
i:for (let i = 1; i <= amount; i++) {对于每个金额
i，尝试计算兑换该金额所需的最少硬币数量。 -
遍历每一个硬币
coin:for (let coin of coins) {对于每个硬币
coin，检查是否可以用该硬币兑换当前金额i。 -
更新
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。 -
返回结果:
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
-
索引从 0 开始:
JavaScript 数组的索引从 0 开始。如果我们只创建一个长度为amount的数组，那么我们只能存储从 0 到amount - 1的值，而无法存储amount本身的值。 -
包含所有子问题:
动态规划的核心思想是通过解决子问题来解决原问题。为了能够解决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 的所有子问题的解，从而能够正确地解决整个问题。
这篇关于算法刷题 322. 零钱兑换的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
