笔试面试高频题。力扣上也有道原题：70. 爬楼梯，但是用斐波那契递归会超时，只能用方法一。

滚动数组递推解法:

时间复杂度 ：$O(N)$

空间复杂度 ：$O(1)$

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;

    int p = 0, q = 0, r = 1;
    for (int i = 1; i <= n; i ++ )
    {
        p = q;      //每次循环中p表示跳到第i-2级台阶的方案数
        q = r;      //q表示跳到第i-1级台阶的方案数
        r = p + q;  //r表示跳到第i级台阶的方案数
    }

    cout << r << endl;

    return 0;
}

斐波那契递归解法：

时间复杂度 ：$O(N)$

空间复杂度 ：$O(N)$

#include <iostream>

using namespace std;

int ans = 0, n;

int f(int k)    //其实就是斐波那契数列，因为要跳到第n级台阶，必须从n-1或n-2级台阶起跳
                //那么跳到第n级台阶的方案就等于跳到第n-1级台阶的方案加跳到第n-2级台阶的方案，即斐波那契数列
{
    if (k == n) ans ++ ;
    else if (k < n)
    {
        f(k + 1);
        f(k + 2);
    }
}

int main()
{
    cin >> n;

    f(0);

    cout << ans << endl;

    return 0;
}