代码随想录算法训练营第四十八天| 70. 爬楼梯 （进阶）、322. 零钱兑换、279.完全平方数

 70. 爬楼梯 （进阶）

题目链接：70. 爬楼梯 （进阶）

文档讲解：代码随想录/爬楼梯 （进阶）

状态：已完成（0遍）

解题过程 

这几天博主忙着面试和入职，一晃已经周四了，这个礼拜的卡我先补上，只更新一下各个链接，其他的等博主二刷的时候再补充。

看完代码随想录之后的想法 

这道题没有JS版本的解。

---

 322. 零钱兑换

题目链接：518. 零钱兑换

文档讲解：代码随想录/零钱兑换

视频讲解：视频讲解-零钱兑换

状态：已完成（1遍）

解题过程  

 看完代码随想录之后的想法 

讲解代码如下：

const coinChange = (coins, amount) => {if(!amount) {return 0;}let dp = Array(amount + 1).fill(Infinity);dp[0] = 0;for(let i = 0; i < coins.length; i++) {for(let j = coins[i]; j <= amount; j++) {dp[j] = Math.min(dp[j - coins[i]] + 1, dp[j]);}}return dp[amount] === Infinity ? -1 : dp[amount];
}

这是遍历物品的版本，下面是遍历背包的版本。

var coinChange = function(coins, amount) {const dp = Array(amount + 1).fill(Infinity)dp[0] = 0for (let i = 1; i <= amount; i++) {for (let j = 0; j < coins.length; j++) {if (i >= coins[j] && dp[i - coins[j]] !== Infinity) {dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1)}}}return dp[amount] === Infinity ? -1 : dp[amount]
}

 

---

279.完全平方数

题目链接：279.完全平方数

文档讲解：代码随想录/完全平方数

视频讲解：视频讲解-完全平方数

状态：已完成（1遍）

解题过程  

看完代码随想录之后的想法 

讲解代码如下：

// 先遍历物品，再遍历背包
var numSquares1 = function(n) {let dp = new Array(n + 1).fill(Infinity)dp[0] = 0for(let i = 1; i**2 <= n; i++) {let val = i**2for(let j = val; j <= n; j++) {dp[j] = Math.min(dp[j], dp[j - val] + 1)}}return dp[n]
};
// 先遍历背包，再遍历物品
var numSquares2 = function(n) {let dp = new Array(n + 1).fill(Infinity)dp[0] = 0for(let i = 1; i <= n; i++) {for(let j = 1; j * j <= i; j++) {dp[i] = Math.min(dp[i - j * j] + 1, dp[i])}}return dp[n]
};