题目：509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯
参考链接：代码随想录
理论基础
DP就是一个状态由上一个子状态推导出来的问题，区别贪心主要由一个状态推导的过程。
解题五部曲：
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
debug方法：
打印DP数组，检查推导思路是否正确
509. 斐波那契数
思路：五部曲来走，第一步dp数组，dp[i]即第i个数的F(i)；递推公式即为dp[i]=dp[i-1]+dp[i-2]，直接给出来了；初始化，也就是dp[0]和dp[1]，直接给出；遍历顺序，直接由递推公式看出，从前往后遍历；举例推导，这个比较容易，这题就不举例了。时间复杂度O(2^n)。注意求递归算法的时间复杂度，就是看递归调用了多少次，对于斐波那契数，第一层调用1次，第二层2次，第三层4次，加起来就是等比数列求和公式，为O(2^n)。
class Solution {
public:
int fib(int n) {
if(n<=1){
return n;
}
return fib(n-2)+fib(n-1);
}
};
递归代码很容易写出，看完标答也可以直接从头开始一个个往后求解。时间复杂度只要O(n)，空间复杂度只要O(1)。
代码如下：
class Solution {
public:
int fib(int N) {
if (N <= 1) return N;
int dp[2];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= N; i++) {
int sum = dp[0] + dp[1];
dp[0] = dp[1];
dp[1] = sum;
}
return dp[1];
}
};
70. 爬楼梯
思路：这题一开始没思路，因为不够直观，我们采用DP五部曲。首先思考爬1层楼梯，有1种方法，爬2层楼梯，有2种方法，而爬3层，就是爬第一层，再跨两步，或者爬2层，再跨一步。本题只需要求出方法数，故dp数组表示爬第i层需要的方法数；递归公式，dp[i]=dp[i-1]+dp[i-2]，即先爬i-1层加1步或者先爬i-2层加2步；初始化比较容易；遍历顺序也是从少到多；举例比较容易。如果不用递归，时间复杂度O(n)。
class Solution {
public:
int climbStairs(int n) {
if(n<=2){
return n;
}
int dp1=1,dp2=2;
for(int i=3;i<=n;i++){
int sum=dp1+dp2;
dp1=dp2;
dp2=sum;
}
return dp2;
}
};
746. 使用最小花费爬楼梯
思路：同样DP五部曲。首先是dp数组，dp[i]记录爬到i台阶需要的最小cost，注意本题是求最小体力，故dp必须时刻记录最小；然后是递推公式，可以从dp[i-1]走一步花费cost[i-1]，或者从dp[i-2]走两步花费cost[i-2]，二者取min；初始化，本题说可以从0或1开始，说明到达0和1是不收费的，故dp[0]和dp[1]都初始化为0；遍历顺序从低到高；举例略。时间复杂度O(n)。
这些题目的遍历顺序都比较直观，后续还有遍历顺序不好确定的题目。
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
//本题cost长度至少为2，故不要单独返回0和1
int dp[2];
dp[0]=0;
dp[1]=0;
for(int i=2;i<=cost.size();i++){
int sum=min(dp[0]+cost[i-2],dp[1]+cost[i-1]);
dp[0]=dp[1];
dp[1]=sum;
}
return dp[1];
}
};
