力扣HOT100之动态规划：70. 爬楼梯

这道题得用动态规划来做，用递归好像会超时。还是继续使用代码随想录中的动规五部曲：
1.确定dp[i]的含义:爬到第i阶楼梯的方法数
2.确定递推公式:dp[i] = dp[i - 1] + dp[i - 2]
3.dp数组初始化:dp[0] = 1, dp[1] = 1
4.确定遍历顺序：从前往后遍历
5.打印数组(省略)
由于本题使用的是一维dp数组，因此dp[i]的意义为：爬到第i节楼梯共有dp[i]种方法。由于这本质上就是一个斐波那契数列，所以递推公式也很好想，只有到达第i阶只有两个情况：

1. 先设法到达i - 1阶，再向上爬一级
2. 先设法到达i - 2阶，再向上爬两级
   因此爬到第i阶的方法数为爬到i - 1阶和爬到i - 2阶的方法数之和。
   dp数组初始化仅对dp[0]和dp[1]进行赋值，都赋值为1。然后从前往后不断更新dp数组，最终返回dp[n]即可。

class Solution {
public:int climbStairs(int n) {//动规五部曲//1.确定dp[i]的含义:爬到第i阶楼梯的方法数//2.确定递推公式:dp[i] = dp[i - 1] + dp[i - 2]//3.dp数组初始化:dp[0] = 1, dp[1] = 1//4.确定遍历顺序：从前往后遍历//5.打印数组(省略)vector<int> dp(n + 1);   //初始化dp[0] = 1;dp[1] = 1;for(int i = 2; i <= n; i++)dp[i] = dp[i - 1] + dp[i - 2];return dp[n];}
};