剑指offer（二）

1.一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

    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.题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

class Solution {
public:
    int jumpFloorII(int number) {
        if(number==1){
            return 1;
        }
        return 2*jumpFloorII(number-1);
    }
};

3.矩形覆盖
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2n的大矩形，总共有多少种方法？
：覆盖方法有两种（12或者是2*1），所以总方法就是这两种方法之和，通过规律可知fn = fab(4)+fab(3),fab时求斐波那契数列的函数。f1=1+0;f2=1+1;f3=2+1;f4=3+2

public class Solution {
    public int RectCover(int target) {
        if(target==0){
            return 0;
        }
        int a=0;
        int b=1;
        int c=0;
        while(target>0){
            c=a;
            a=b;
            b=c+b;
            target-=1;
        }
        return a+c;
    }
}