https://programmercarl.com/0070.%E7%88%AC%E6%A5%BC%E6%A2%AF.html

视频：https://www.bilibili.com/video/BV17h411h7UH

1.本题和斐波那契数列是一个类型的，关键点在于想到当我们想去第i层的时候，我们只需要知道第 i - 1 和i - 2层的方式数即可，因为一个是想到这个在i - 1的位置加1即可到下一层同理可得在i - 2的位置加2也可以到达。

CPP

class Solution {
public:
    int climbStairs(int n) {
        if(n <= 2)return n;
        int dp[3];
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i <=n; i++){
            int sum = dp[1] + dp[2];
            dp[1] = dp[2];
            dp[2] = sum;
        }
        return dp[2];
    }
};