咳咳, 因为找实习+摆导致时间被浪费大半;
先从动态规划学起吧,之前的慢慢补。
理论基础
动态规划的解题步骤
1.确定dp数组及对应下标的含义
2.确定dp的状态转移方程(递推公式)
3.确定dp数组如何初始化
4.确定dp遍历顺序
5.距离推导dp数组验证
509. 斐波那契数
题目链接:https://leetcode.cn/problems/fibonacci-number/
1.dp[i]含义为数列中第i个数
2.dp[i] = dp[i-1]+dp[i-2]
3.dp[0] = 0; dp[1] =1
4.从dp[2]开始顺序
5.显然
/**
* @param {number} n
* @return {number}
*/
//dp五步走
//1.dp数组含义
//2.dp公式
//3.dp初始化
//4.dp顺序
//5.dp验证
var fib = function(n) {
//1.dp[i]含义为数列中第i个数
//2.dp[i] = dp[i-1]+dp[i-2]
//3.dp[0] = 0; dp[1] =1
//4.从dp[2]开始顺序
//5.显然
if(n == 0){
return 0
}
if(n == 1){
return 1
}
let dp = new Array(n+1).fill(0)
dp[0] = 0
dp[1] = 1
for(let i = 2; i<=n;i++){
dp[i] = dp[i-1]+dp[i-2]
}
return dp[n]
};
//有坑, n并不是第n个数,而是第n+1个
70. 爬楼梯
题目链接:https://leetcode.cn/problems/climbing-stairs/
1.dp[i]代表到第i+1级台阶的方法(i从0起)
2.dp[i] = dp[i-1]+dp[i-2]
3.dp[0] = 1; dp[1] = 2
4.顺序遍历
5.验证
/**
* @param {number} n
* @return {number}
*/
//1.dp[i]代表到第i+1级台阶的方法(i从0起)
//2.dp[i] = dp[i-1]+dp[i-2]
//3.dp[0] = 1; dp[1] = 2
//4.顺序遍历
//5. 验证
var climbStairs = function(n) {
let dp = new Array(n)
dp[0] = 1
dp[1] = 2
for(let i = 2; i<n;i++){
dp[i] = dp[i-1] + dp[i-2]
}
//忽略越界
return dp[n-1]
};
746. 使用最小花费爬楼梯
题目链接:https://leetcode.cn/problems/min-cost-climbing-stairs/
1.dp[i] 表示第i级(0)台阶的最低花费
2.dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
3.dp[0] = 0; dp[1] = 0
4.顺序遍历
5.验证,发现对"楼梯顶部"理解有问题
/**
* @param {number[]} cost
* @return {number}
*/
//1.dp[i] 表示第i级(0)台阶的最低花费
//2.dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
//3.dp[0] = 0; dp[1] = 0
//4.顺序遍历
var minCostClimbingStairs = function(cost) {
let dp = new Array(cost.length+1).fill(0)
dp[0] = 0
dp[1] = 0
for(let i = 2; i<=cost.length;i++){
dp[i] = Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
}
return dp[cost.length]
};
//犯错: 楼梯顶部不是dp[cost.length-1]而是dp[cost.length]最后一节也要向上爬