By

题目描述1

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

题目解析1

很明显可以发现jumpFloor(n)=jumpFloor(n-1)+jumpFloor(n-2)，于是就写了递归，代码效率超级低，代码如下：

1
2
3
4
5
6
7
8
class Solution {
public:
    int jumpFloor(int number) {
        if(number==1) return 1;
        if(number==2) return 2;
        return (jumpFloor(number-1)+jumpFloor(number-2));
    }
};

实际上，你会发现这其实是个斐波那契数列，具体解答可以参考我的矩阵快速幂解斐波那契数列。这里写出了迭代的方法，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int jumpFloor(int number) {
        if(number==1) return 1;
        if(number==2) return 2;
        int f1=2,f2=1;
        for(;number-2>0;number--){
            f1+=f2;
            f2=f1-f2;
        }
        return f1;
    }
};

题目描述2

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

题目解析2

这题看起来好像比上面那题要难了不少，其实他是一个等比数列，1 2 4 8 16，2的(number-1)次方。于是写了一行代码，代码如下：

1
2
3
4
5
6
class Solution {
public:
    int jumpFloorII(int number) {
        return 1<<--number;
    }
};