代码随想录算法训练营day32

代码随想录算法训练营

—day32

---

前言

今天是算法营的第32天，希望自己能够坚持下来！
开始动态规划章节了，今日任务：
● 动态规划理论基础
● 509. 斐波那契数
● 70. 爬楼梯
● 746. 使用最小花费爬楼梯

---

一、动态规划理论基础

文章讲解
视频讲解

动态规划刷题大纲：

动态规划需要有一个推导公式，每一步都是由上一个状态推导出来的。

动态规划五步曲：

1. 确定dp数组以及下标的含义
2. 确定递归公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

做动规的题目，写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果。

---

二、509. 斐波那契数

题目链接
文章讲解
视频讲解

思路：

1. dp[i]的定义为：第i个数的斐波那契数值是dp[i]
2. 递归公式：题目已经把递推公式直接给我们了：dp[i] = dp[i - 1] + dp[i - 2]
3. 初始化：dp[0] = 0, dp[1] = 1
4. 遍历顺序:因为递推公式是从前往后的，所以遍历顺序是从前往后

动态规划

代码如下：

class Solution {
public://动态规划//dp[i]就是第i个斐波那契数//递推公式：dp[i] = dp[i-1] + dp[i-2];//初始化：dp[0] = 0, dp[1] = 1//遍历顺序：从头到尾int fib(int n) {if (n <= 1) return n;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];}
};

---

动态规划优化空间版

因为结果只由前两项决定，所以不需要维护数组，只需要维护三个变量
代码如下：

class Solution {
public://动态规划//dp[i]就是第i个斐波那契数//递推公式：dp[i] = dp[i-1] + dp[i-2];//初始化：dp[0] = 0, dp[1] = 1//遍历顺序：从头到尾int fib(int n) {if (n <= 1) return n;//因为结果只由前两项决定，所以不需要维护数组，只需要维护三个变量int dp[2];dp[0] = 0; //f[n-2]dp[1] = 1; //f[n-1]for  (int i = 2; i <=n; i++) {int sum = dp[0] + dp[1]; //f[n] = f[n-1] + f[n-2]dp[0] = dp[1]; //更新f[n-2]dp[1] = sum; //更新f[n-1]}return dp[1];}
};

---

递归法

这道题也可以用递归法，代码更加简洁：

class Solution {
public://递归法int fib(int n) {if (n < 2) return n;return fib(n - 1) + fib(n - 2);}
};

---

三、70. 爬楼梯

题目链接
文章讲解
视频讲解

动态规划

思路：

1. dp[i]的定义为： 爬到第i层楼梯，有dp[i]种方法
2. 递归公式：因为dp[i]都是由i-1走一层或者i-2走两层到达的，而dp[i-1]就是走到i-1层的方法，dp[i-2]就是走到i-2层的方法，那么走到i层就是dp[i-1] + dp[i-2]种方法。
   dp[i] = dp[i-1] + dp[i-2];
3. 初始化：dp[1] = 1，dp[2] = 2，dp[0]没有含义，题目也说了n是大于0的，所以递推从1开始，初始化1,2，遍历从3开始。
4. 遍历顺序:因为递推公式是从前往后的，所以遍历顺序是从前往后
5. 举例推导dp数组：
   

代码如下：

class Solution {
public:int climbStairs(int n) {if (n <= 2) 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];}
};

动态规划空间优化

这道题也是只跟i-1和i-2有关，所以只需要维护3个变量就可以了。

代码如下：

class Solution {
public:int climbStairs(int n) {if (n <= 2) return n;int dp[3]; //优化空间dp[1] = 1;dp[2] = 2;for (int i = 3; i <= n; i++) {int sum = dp[1] + dp[2];dp[1] = dp[2];dp[2] = sum;}return dp[2];}
};

---

746. 使用最小花费爬楼梯

题目链接
文章讲解
视频讲解

思路：

1. dp[i]的定义为：代表走到第i台阶需要花费多少
2. 递归公式：第i台阶通过第i-1台阶走一步或者第i-2台阶走两步到达，取两者花费最小为最优解dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
3. 初始化：默认第一步不花费体力，第一步从下标0或者1开始， dp[0] = 0, dp[1] = 0
4. 遍历顺序:因为递推公式是从前往后的，所以遍历顺序是从前往后

代码如下：

class Solution {
public://d[i]含义：代表走到第i台阶需要花费多少//递推公式，第i台阶通过第i-1台阶走一步或者第i-2台阶走两步到达，取两者花费最小为最优解int minCostClimbingStairs(vector<int>& cost) {if (cost.size() < 2) return 0;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()];}
};

---

动态规划空间优化

同样可以优化空间：

class Solution {
public://d[i]含义：代表走到第i台阶需要花费多少//递推公式，第i台阶通过第i-1台阶走一步或者第i-2台阶走两步到达，取两者花费最小为最优解int minCostClimbingStairs(vector<int>& cost) {if (cost.size() < 2) return 0;int dp[2]; //优化空间dp[0] = 0; //默认第一步不花费体力dp[1] = 0;for (int i = 2; i <= cost.size(); i++) {int sum = min(dp[1] + cost[i - 1], dp[0] + cost[i - 2]);dp[0] = dp[1];dp[1] = sum;}return dp[1];}
};

---

总结

动态规划第一天！第一次接触动态规划，牢记动态规划五步曲：

1. 确定dp数组以及下标的含义
2. 确定递归公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

一些小总结：

1. 想不明白的时候需要回归dp数组下标含义再理解一下。
2. 初始化的时候如果遇到像是dp[0]没有含义的时候，试试从后面的dp[1]dp[2]比较明确初始化的下标开始初始化和递推。
3. 当递推公式只涉及i-1,i-2的时候，可以缩小数组大小，只维护最小的数组来节省空间。

明天继续加油！