【剑指offer】10 矩形覆盖

题目地址：矩形覆盖

题目描述                                   

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

 

比如n=3时，2*3的矩形块有3种覆盖方法：

 

题目示例                                   

输入：

4

返回值：

5

解法分析                                   

这道题同样是考察斐波那契数列，思路：我们可以假设大矩形是横放的（高固定为2，宽为n），这时可以看出，小矩形竖着放占用1单位宽度，横着放占用2单位宽度，是不是很熟悉？没错，与青蛙跳台阶一个思路，竖着放就是跳一节台阶，横着放就是跳2节台阶，那么算法自然而然就出来了。

代码                                         

算法1：

function rectCover(number)
{
    // write code here
    if(number<=3){
        return number;
    }else{
        var fib = [];
        fib[1] = 1;
        fib[2] = 2;
        fib[3] = 3;
        for(var i=4;i<=number;i++){
            fib[i]=fib[i-2]+fib[i-1];
        }
        return fib[number];
    }
}

算法2：

function rectCover(number)
{
    // write code here
    if(number==0)return 0;
    var res = 1, mid = 1;
    while(number--){
        mid+=res;
        res=mid-res;
    }
    return res;
}

执行结果