代码随想录day38【动态规划】 斐波那契数 爬楼梯 使用最小花费爬楼梯

动态规划理论基础

解题模版：动规五部曲

1. 确定dp数组下标的含义
2. 确定递推公式
3. 确定初始值
4. 确定遍历顺序
5. 举例推到

最好将每一步打印下来。

斐波那契数

力扣题目链接

var fib = function(n) {
    let dp=[]
    dp[0]=0
    dp[1]=1

    for(let i=2;i<=n;i++){
        dp[i]=dp[i-1]+dp[i-2]
    }
    return dp[n]
};

爬楼梯

力扣题目链接

var climbStairs = function(n) {
    let dp=[]
    dp[0]=0
    dp[1]=1;
    dp[2]=2;
    for(let i=3;i<=n;i++){
        dp[i]=dp[i-1]+dp[i-2]
    }
    return dp[n]
};

使用最小花费爬楼梯

力扣题目链接
自己的分析：

1. dp 数组：到达第i梯的最低花费
2. 状态转移方程： dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
3. 初始状态： dp[0] dp[1] 均为0，不需要花销
4. 遍历顺序：顺序
   bingo！

var minCostClimbingStairs = function(cost) {
    let dp = [];
    // dp[i] 到达第i梯的最低花费
    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[dp.length - 1];
};