对于第n个台阶，要么从第n-1个台阶一步跨过来，要么从第n-2个台阶一步跨过来（从第n-2个台阶先走一个台阶再走一个台阶的情况，包含在了从第n-1个台阶走一个台阶的情况中了）。所以说有f(n)=f(n-1)+f(n-2)，边界值为f(1)=1，f(2)=2。此时，跳台阶问题可以完全转化为斐波那契数列问题。

方法一

递归
已知斐波那契数列的公式为f(n)=f(n-1)+f(n-2)。要求f(n)就需要知道f(n-1)和f(n-2)，而求f(n-1)需要f(n-2)和f(n-3)，依次推导，直到题目给出的边界{f(1)=1,f(2)=2}。
图解如下：

具体代码如下：

class Solution {
public:
    int jumpFloor(int number) {
        if (number==1 || number==2) return number;//边界条件。
        return jumpFloor(number-1)+jumpFloor(number-2);//递归步骤。
    }
};

时间复杂度：O(2^N)。
空间复杂度：递归栈的空间。

方法二

可以发现方法一中f(n-2)，f(n-3)等等都出现了重复计算的情况，如图所示。

所以可以使用一个数组将其记录下来，在下一次遇到时直接调用，不需要重复计算。
代码如下：
···
class Solution {
public:

int fb(int n, vector<int>& f){
    if (n==1 || n==2) return n;
    if (f[n] != -1) return f[n];
    return f[n] = fb(n-1, f) + fb(n-2, f);
}

int jumpFloor(int number) {
    vector<int> f(100,-1);
    return fb(number, f);
}

};
···
时间复杂度：O(N)。
空间复杂度：O(N)加递归栈的空间。

方法三

递推
与递归的思路相反，在已知f(1)和f(2)的情况下，我们可以计算出f(3)；在已知f(2)和f(3)的情况下，我们可以计算出f(4)；以此类推，已知f(n-2)和f(n-1)的情况下，我们可以计算出f(n)。
示意图如下：

具体代码如下：
···
class Solution {
public:

int jumpFloor(int number) {
    if (number==1 || number==2) return number;

    vector<int> f(100,0);//存储计算过的f(i)。
    f[1] = 1;
    f[2] = 2;
    for (int i=3;i<=number;i++){
        f[i] = f[i-1]+f[i-2];
    }
    return f[number];
}

};
···
时间复杂度：O(N)。
空间复杂度：O(N)，用了一个数组存储数列各项。

方法四

可以看到方法三中，每一个f(i)只参加了2次加法运算，之后便不再被使用。于是我们可以使用两个变量a，b而非数组，来记录当前循环需要的两个数列项，并在循环过程中对变量进行更新，用新值覆盖旧值。
具体代码如下：

class Solution {
public:

    int jumpFloor(int number) {
        if (number==1 || number==2) return number;
        int a=1,b=2,c=0;
        for (int i=3;i<=number;i++){
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
};

时间复杂度：O(N)。
空间复杂度：O(1)。