本文共 1178 字，大约阅读时间需要 3 分钟。

剑指offer——跳台阶&&变态跳台阶&&矩形覆盖

1.跳台阶

哈哈哈，递归题，一遍过

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

2.变态跳台阶

复杂度这么高竟然也可以AC，666

Solution1：

class Solution {public:    int jumpFloorII(int number) {        if(number==1)            return 1;        else if(number==2)            return 2;        else{            int all=0;            while(number>=2)                all+=jumpFloorII(--number);            return all+1;//考虑到从第0层直接跳到第n层的情况，故应该+1        }    }};

Solution2：参考网址

因为n级台阶，第一步有n种跳法：跳1级、跳2级、到跳n级 跳1级，剩下n-1级，则剩下跳法是f(n-1) 跳2级，剩下n-2级，则剩下跳法是f(n-2) 所以f(n)=f(n-1)+f(n-2)+…+f(1) 因为f(n-1)=f(n-2)+f(n-3)+…+f(1) 所以f(n)=2*f(n-1)

return  1<<--number;

后的数学规律才是真牛逼啊

3.矩形覆盖

本质上还是斐波那契额数列，但稍有不同。一开始竟然没看出来。。

class Solution {public:    int rectCover(int number) {        int f=1,g=2;        if(number==0)            return 0;        else if(number==1)             return f;        else if(number==2)            return g;        while(1<--number){            g=g+f;            f=g-f;        }        return g;    }};

转载地址：http://mthdb.baihongyu.com/