爬楼梯

两种方法：

1. 斐波那契数列（找规律——爬1层1种，2层2种，3层3种，4层5种...）
2. 动态规划

有必要总结一下找规律的解法：这种解法需要细心和耐心，我们一般取出前3种情况看一下规律，如果规律不明显，可以增加情况，直到过于复杂才放弃此解法。PS：前几种情况同样可以用来检验算法的正确性

动态规划——设dp[i]表示第i层的跳法，状态公式如下：

1. 如果i>1，dp[i] = dp[i-2] + dp[i-1])
2. 基准1: dp[0]=0
3. 基准2: dp[1]=1
4. 基准3: dp[2]=2

状态公式的解释：

1. 最后一步跨越一个或两个台阶，因此dp[i] = dp[i-2] + dp[i-1])
2. 0个阶梯步数为0
3. 1个阶梯步数为1
4. 2个阶梯步数为2

为什么会有这么多基准条件呢？因为动态规划的本质是数学归纳法，而数学归纳法对于基准条件是没有限制的，因此基准条件具体应该设置多少个需要我们列举出最前面几种情况，再做一个综合判断

动态规划解法代码如下：

//
// Created by jt on 2020/8/30.
//
#include <vector>
using namespace std;

class Solution {
public:
    /**
     *
     * @param n int整型
     * @return int整型
     */
    int climbStairs(int n) {
        // write code here
        vector<int> dp(n+1, 0);
        dp[1] = 1; dp[2] = 2;
        for (int i = 3; i <= n; ++i) {
            dp[i] = dp[i-2] + dp[i-1];
        }
        return dp[n];
    }
};

斐波那契数列解法代码如下：

//
// Created by jt on 2020/8/30.
//
class Solution {
public:
    /**
     *
     * @param n int整型
     * @return int整型
     */
    int climbStairs(int n) {
        // write code here
        int i = 0, j = 1;
        while(n--) {
            int k = i + j;
            i = j;
            j = k;
        }
        return j;
    }
};