对于第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)。