代码随想录算法训练营第三十八 |● 509. 斐波那契数 ● 70. 爬楼梯 ● 746. 使用最小花费爬楼梯

我在每一个算法开始之前都会去认真的看一下这个理论基础，或者说是算法的主要思想，可以直接看视频carl讲解的很清晰；其次还会大致看一下这一part中的题型及难度
动态规划理论基础讲解链接：https://programmercarl.com/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

视频：https://www.bilibili.com/video/BV13Q4y197Wg

509. 斐波那契数

https://programmercarl.com/0509.%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0.html
视频：https://www.bilibili.com/video/BV1f5411K7mo

class Solution {
public:int fib(int n) {if(n<=1) return n;//dp[i] 第i个斐波那契数值为dp[i]vector<int> dp(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. 爬楼梯

https://programmercarl.com/0070.%E7%88%AC%E6%A5%BC%E6%A2%AF.html
视频：https://www.bilibili.com/video/BV17h411h7UH

class Solution {
public:int climbStairs(int n) {//dp[i]表示  爬到第i层楼梯，有dp[i]种方法//上i-1层楼梯，有dp[i - 1]种方法，i层就加一//dp[i] = dp[i-1]+dp[i-2]if(n<=1) return n;//希望从i=1开始vector<int> dp(n+1);    //犯了个低级错误定义成了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. 使用最小花费爬楼梯

https://programmercarl.com/0746.%E4%BD%BF%E7%94%A8%E6%9C%80%E5%B0%8F%E8%8A%B1%E8%B4%B9%E7%88%AC%E6%A5%BC%E6%A2%AF.html
视频讲解：https://www.bilibili.com/video/BV16G411c7yZ

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {vector<int> dp(cost.size()+1);dp[0] = 0;dp[1] = 0;for(int i=2; i<=cost.size();i++) {dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);}return dp[cost.size()];}
};