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

动态规划

重叠子问题和最优子结构

由前一个状态推导后一个状态

dp数组

做题：

1. 确定dp数组和下标意义

2. 确定递推公式

3. dp数组如何初始化

4. 确定遍历顺序

5. 举例推导dp数组

509. 斐波那契数

五步：1. dp数组：第i个数的值是dp[i]。2.dp[i]=dp[i-1]+dp[i-2]。3. dp[0]=0,dp[1]=1。4. 从前往后遍历。5. 0 1 1 2 3 5 8 13 21 34 55

class Solution {
public: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];}
};

70. 爬楼梯

五步：1. dp数组：爬到第i阶的方法数是dp[i]。2.dp[i]=dp[i-1]+dp[i-2]。3. dp[1]=1,dp[2]=2，i=0时没有意义。4. 从前往后遍历。5. 1 2 3 5 8 13 21 34 55

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];}
};

746. 使用最小花费爬楼梯

五步：1. dp数组：爬到第i阶的花费是dp[i]。2.dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])。3. dp[0]=0,dp[1]=0。4. 从前往后遍历。5.

dp数组的最后一项是楼顶

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<dp.size();i++){dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);}return dp[dp.size()-1];}
};