写点什么

LeetCode 题解:322. 零钱兑换,动态规划,JavaScript,详细注释

用户头像
Lee Chen
关注
发布于: 2021 年 02 月 23 日
LeetCode题解:322. 零钱兑换,动态规划,JavaScript,详细注释

原题链接:https://leetcode-cn.com/problems/coin-change/


解题思路:


  1. 用硬币凑到amount,就是从0元,一直累加到amount元的过程。

  2. 我们可以创建一个dp数组,长度是amount + 1,用它的索引表示金额,dp[i]存储的是凑到金额i所需的最小硬币数量。

  3. 对于金额i,我们需要把coins中的硬币都试一次,也就是从金额i - coins[j],用1coins[j]面额的硬币凑过来。

  4. 状态转移方程:dp[i] = Math.min(dp[i], dp[i - coin] + 1);


/** * @param {number[]} coins * @param {number} amount * @return {number} */var coinChange = function (coins, amount) {  // 兑换的金额是amount,因此需要从0开始递推到amount  // 由于要计算的是最小值,因此初始化为Infinity,避免计算错误  let dp = new Array(amount + 1).fill(Infinity);  dp[0] = 0; // 金额为0时,硬币数为0,用于第一次使用硬币
// 从1开始才会累计硬币个数 for (let i = 1; i < dp.length; i++) { // 需要计算各种硬币的组合情况 for (const coin of coins) { // 向前查找硬币的使用情况,当前金额是由金额i - coin加上coin而来,需要至少保证金额大于0 // i - coin === 0 时,是第一次使用当前硬币 if (i - coin >= 0) { // 如果要凑成当前金额,例如11,它可能的是由10+1,9+2,6+5组合而成 dp[i] = Math.min( dp[i], // 表示已存储了之前所有硬币组合的最小值 // 表示当前硬币组合的硬币个数 // 当前硬币个数,是由金额i - coin加上一个coin硬币而来 // 因此数量就是dp[i - coin]的硬币数加1 dp[i - coin] + 1, ); } } }
// 如果硬币无法凑成所需金额,就会出现从amount向前查找任意硬币金额都只能找到Infinity的情况 // 因此最后一位必然还是Infinity return dp[amount] === Infinity ? -1 : dp[amount];};
复制代码


发布于: 2021 年 02 月 23 日阅读数: 8
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:322. 零钱兑换,动态规划,JavaScript,详细注释