代码随想录Day38-Leetcode509. 斐波那契数，70. 爬楼梯，746. 使用最小花费爬楼梯

咳咳, 因为找实习+摆导致时间被浪费大半;
先从动态规划学起吧,之前的慢慢补。

理论基础

动态规划的解题步骤
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]最后一节也要向上爬