写点什么

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

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

原题链接:518. 零钱兑换 II


解题思路:


  1. 假设输入: amount = 5, coins = [1, 2, 5],如果用长度为amount + 1dp数组递推,需要满足如下特性:

* 如果用长度为amount + 1dp数组递推。

* 每个索引代表了递推到的金额。

* 每个元素是硬币组合数。

* 0位置是初始状态,设置为1,表示都从1种组合数开始递推。


  1. 我们可以将其按照硬币种类拆分递推结果:

* 硬币1[1,1,1,1,1,1]

* 硬币2[1,0,1,0,1,0]

* 硬币5[1,0,0,0,0,1]

* 硬币12[1,1,2,2,3,3]

* 硬币125[1,1,2,2,3,4]


  1. 递推方法如下:

* 依次计算每个硬币面额coin的递推结果。

* 当前金额i,是从i - coin添加了coin而来。

* 当前新的硬币组合数dp[i],等于上一种硬币递推到i的组合数dp[i],加上i - coin的组合数dp[i - coin]而来。

* 状态转移方程为:dp[i] = dp[i] + dp[i - coin]


/** * @param {number} amount * @param {number[]} coins * @return {number} */var change = function (amount, coins) {  // 不断使用硬币组合,从0元一只组合到amount  // 数组保存的是每个金额可用的硬币组合数量  // 初始状态因为都没有递推,都为0  let dp = new Array(amount + 1).fill(0);  // 0位置设置为1,因为第一次递推都是从金额为coin开始  // 状态转移方程为dp[i] = dp[i] + dp[i - coin],这样dp[coin]的初始值就为dp[0]  // 由于第一次要投一个硬币,因此dp[0] = 1,能保证正常递推  dp[0] = 1;
// 分别计算每个硬币可以组合成amount的方法数量 for (const coin of coins) { // 小于coin的金额是无法通过coin组合而成 // 一直递推到amount,就知道当前硬币组合成amount有多少种方法 for (let i = coin; i <= amount; i++) { dp[i] = // 保留之前硬币可以组合出当前金额的方法数量 dp[i] + // 当前金额,必然是从i-coin,添加coin金额硬币之后组合而成 // 也就是当前金额是在i-coin的基础上变化而来,因此需要带上i-coin的组合数量 dp[i - coin]; } }
// 最后组合成amount的方法数,就在amount位置 return dp[amount];};
复制代码


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

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

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