代码随想录打卡Day32

今天有点事，先做一题，剩下的明天补。

509. 斐波那契数

这道题目太简单了，递归几行代码就结束了，用动态规划做也可以，主要是学习一下动态规划五部曲。
这是递归的代码

class Solution {
public:int fib(int n) {//确定终止条件if(n == 0) return 0;if(n == 1) return 1;return fib(n - 1) + fib(n - 2); }
};

这是动态规划的代码

class Solution {
public:int fib(int n) {//1.确定dp[i]的含义：斐波那契数列第i个数的值//2.确定递推公式  dp[i] = dp[i - 1] + dp[i - 2]//3.dp数组初始化 dp[0] = 0, dp[1] = 1//4.确定遍历顺序：从前往后遍历//5.打印数组(省略)if(n < 2) return n;//大于等于2的情况vector<int> dp(2);int sum;dp[0] = 0;dp[1] = 1;for(int i = 2; i <= n; i++){sum = dp[0] + dp[1];dp[0] = dp[1];dp[1] = sum;}return dp[1];}
};

先这样。

---

70. 爬楼梯

这道题目之前做过，印象非常深，因为当时还没刷代码随想录，第一次做这种动态规划题，非常烧脑。而且就算搞明白这个本质上是斐波那契数列以后，用递归也做不了，因为递归会超时。。。。爬到第i个台阶的方法数取决于爬到第i-1和i-2阶的方法数之和，就是纯纯的斐波那契数列啊。

class Solution {
public:int climbStairs(int n) {if(n <= 2) return n;vector<int> dp(3);dp[1] = 1;dp[2] = 2;int sum;for(int i = 3; i <= n; i++){sum = dp[1] + dp[2];dp[1] = dp[2];dp[2] = sum;}return dp[2];}};

746. 使用最小花费爬楼梯

这道题目没有看讲解自己AC的，按照动态规划五部曲：
1.确定dp[i]的含义：爬到下标为i台阶所需的最小花费；
2.确定递推公式 dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])；
3.dp数组初始化 dp[0] = 0, dp[1] = 0 （因为开局选择起点的时候不需要花钱）
4.确定遍历顺序：从前往后遍历
5.打印数组(省略)
这道题的核心就在于递推公式的构建，不像之前两道题只是前两项相加那么简单，这道题还需要求二者之间的最小值。

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {//1.确定dp[i]的含义：爬到下标为i台阶所需的最小花费//2.确定递推公式  dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])//3.dp数组初始化 dp[0] = 0, dp[1] = 1//4.确定遍历顺序：从前往后遍历//5.打印数组(省略)vector<int> dp(cost.size() + 1);dp[0] = 0;dp[1] = 0;int sum = 0;//总花费为dp[cost.size()]for(int i = 2; i <= cost.size(); i++){sum = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);dp[i] = sum;}return dp.back();}
};

补完了，享受周末~