【代码随想录】day38
提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
文章目录
- 一、 动态规划理论基础
- 二、 509斐波那契数
- 三、70爬楼梯
- 四、746使用最小花费爬楼梯
一、 动态规划理论基础
- 背包问题
- 打家劫舍
- 股票问题
- 子序列问题
动态规划问题分步：
- dp数组及下标的含义；
- 递推公式；
- dp数组如何初始化
- 遍历顺序
- 打印dp数组
二、 509斐波那契数
（状态压缩版，只保留当前数的前两位就行）
class Solution {
public:int fib(int n) {if (n < 2) {return n;}int a = 0, b = 1;for (int i = 0; i < n - 2; i ++) {int temp = a;a = b;b += temp;}return a + b;}
};
按动规五部曲写：
1.dp数组的含义：dp[i]表示第i个斐波那契数
2.递推公式：f(n) = f(n-1) + f(n-2)
3.dp数组初始化：dp[0] = 0，dp[1] = 1
4.遍历顺序：从前向后
class Solution {
public:vector<int> dp = {0, 1};for (int i = 2; i < n + 1; i ++) {dp.push_back(dp[i-1] + dp[i-2]);}return dp[n];}
};
三、70爬楼梯
可以用斐波那契是因为：一次可以迈一阶或者两阶，所以在第n阶的时候，不是从n-1就是n-2来的。
class Solution {
public:int climbStairs(int n) {int a = 0, b = 1;for (int i = 0; i < n - 1; i ++) {int temp = a;a = b;b += temp;}return a + b;}
};
动规五部曲：
class Solution {
public:int climbStairs(int n) {vector<int> dp = {0, 1, 2};for (int i = 3; i < n + 1; i ++) {dp.push_back(dp[i-1] + dp[i-2]);}return dp[n];}
};
四、746使用最小花费爬楼梯
class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {cost.push_back(0);int n = cost.size();vector<int> dp(n+1);dp[0] = cost[0];dp[1] = cost[1];for (int i = 2; i < n; i ++) {dp[i] = cost[i] + min(dp[i-1], dp[i-2]);}return dp[n-1];}
};