爬楼梯(进阶）
力扣题目链接
改为：一步一个台阶，两个台阶，三个台阶，.......，直到 m个台阶。问有多少种不同的方法可以爬到楼顶呢？
分析：其实就是问装满背包有几种方法。
1阶，2阶，.... m阶就是物品，楼顶就是背包。
var climbStairs = function(n) {
const dp = new Array(n + 1).fill(0);
const m = 2;
dp[0] = 1;
for(let i = 1; i <= n; i++){
for(let j = 1; j <= m; j++){
if(i >= j) {
dp[i] += dp[i - j];
}
}
}
return dp[n];
};
零钱兑换
- dp数组含义：装满容量为j，最少的物品数量为dp[j]
- 递推公式： dp[j]= min(dp[j-cost[i]]+1, dp[j])
- 初始化：
dp[0]=0, 非零下标的均为最大值 - 遍历顺序：
本题求钱币最小个数，那么钱币有顺序和没有顺序都可以，都不影响钱币的最小个数。
var coinChange = function(coins, amount) {
let dp = new 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]);
}
// console.log(dp);
}
console.log(dp[amount]);
return dp[amount]=== Infinity? -1: dp[amount];
};
完全平方数
分析：
思路与上题零钱兑换一致。
力扣题目链接
dp数组含义：
装满和为j，最少的物品数量为dp[j]
递推公式：
dp[j]=min(dp[j],dp[j-i*i]+1)
遍历顺序：均可。
var numSquares = function(n) {
let dp = new Array(n + 1).fill(Infinity); //初始化
dp[0] = 0;
for (var i = 0; i*i <= n; i++) {//注意是<=
//物品
for (let j = i*i; j <= n; j++) {
//背包
dp[j] = Math.min(dp[j - i*i] + 1, dp[j]);
}
}
return dp[n];
};
