青蛙跳台阶问题

题目:一直青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级台阶的总共有多少种跳法?
思路:当n>3时,第一次跳有两种跳法:跳1级,剩余n-1级;跳2级剩余n-2级。所有总的跳法就是f(n) = f(n-1) + f(n-2),可以看出是一个斐波那契数列。

class Solution {
public:
    int jumpFloor(int number) {
        if(number == 1 || number == 2)
            return number;
        return jumpFloor(number-1)+jumpFloor(number-2);
    }
};

拓展:如果青蛙一次可以跳1级,也可以跳2级,…,也可以跳n级,此时有多少种跳法?
其实思路就是一样的,只不过跳法多了一些。 可以这么思考:第一次跳时,可以跳n级;可以跳n-1级,剩余1级;可以跳n-2级,剩余2级;…;可以跳1级,剩余n-1级。 用循环的方法计算,可以很快得到答案,可以避免重复的计算。 其实,通过观察,f(n) = 2^(n-1)
f(1) = 1;
f(2) = 1+f(1);
f(3) = 1+f(1)+f(2);

Leave a Reply

Your email address will not be published. Required fields are marked *