代码随想录算法训练营第四十一天 | 理论基础、509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯

理论基础

代码随想录

视频：从此再也不怕动态规划了，动态规划解题方法论大曝光！| 理论基础 |力扣刷题总结| 动态规划入门_哔哩哔哩_bilibili

动归五部曲

1.dp数组以及下标的含义

2.递推公式

3.dp数组如何初始化

4.遍历顺序(例如先背包再物品，先物品再背包)

5.打印dp数组

509. 斐波那契数

代码随想录

视频：手把手带你入门动态规划 | LeetCode：509.斐波那契数_哔哩哔哩_bilibili

解题思路

1.确定dp[i]含义， dp[i]表示第i个斐波那契数的值

2.递推公式，dp[i] = dp[i-1] + dp[i-2]

3.dp数组如何初始化 dp[0] = 1 , dp[1] = 1

4.确定遍历顺序，从前往后

class Solution {
public:
    int fib(int n) {
      if(n<=1) return n;
      vector<int> dp(n+1);   //0到n一共n+1个数
      dp[0] = 0 ;
      dp[1] = 1;  //初始化
      for(int i = 2 ; i<=n;i++)
      {
         dp[i] = dp[i-1] + dp[i-2];   //递推公式
      }
      return dp[n];
    }
};

70. 爬楼梯

代码随想录

视频：带你学透动态规划-爬楼梯（对应力扣70.爬楼梯）| 动态规划经典入门题目_哔哩哔哩_bilibili

解题思路

到几阶，之前需要看前两阶的方法，第前2阶垮两步即可，第前1阶垮一步即可，所以就是前两阶的方法种数相加

1.dp[i] 达到第i阶楼梯有dp[i]种方法

2. 根据分析 dp[i] = dp[i-1] + dp[i-2]

3.初始化 d[1] = 1

dp[2] = 2

4.从前往后，(递推公式中相加的两个数都是经过计算的)

class Solution {
public:
    int climbStairs(int n) {
     if(n<=1) return n;  //防止空指针
     vector<int> dp(n+1);
     dp[1] = 1;
     dp[2] = 2;
     for(int i=3 ; i<=n ; i++)
     {
        dp[i] = dp[i-1] + dp[i-2];
     }
     return dp[n];
    }
};

746. 使用最小花费爬楼梯

代码随想录

视频讲解：动态规划开更了！| LeetCode：746. 使用最小花费爬楼梯_哔哩哔哩_bilibili

解题思路

1.dp[i] 表示到达第i个台阶所消耗的最少体力

2. dp[i]可以由dp[i-1]+ cost[i-1]和dp[i-2] + cost[i-2]得到，取最小值即可

3.初始化选择初始台阶时，不需要花费体力，只有跳才会花费，因此dp0和1都是0

4.遍历顺序：从前往后，因为都是由前面的台阶跳上来的

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
         vector<int> dp(n+1);
         dp[0] = 0;
         dp[1] = 0;  //选择下标1或者0作为起始，没有体力花费，只有跳了才有花费
         for(int i=2 ; i < n+1 ; i++)
         {
            dp[i] = min( dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
         }
         return dp[n];
    }
};