矩阵覆盖

题目描述

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

function rectCover(number)
{
    var arr = [];
    arr[0] = 0;
    arr[1] = 1;
    arr[2] = 2;
    for(var i=3;i<=number;i++){
        arr[i] = arr[i-1] + arr[i-2];
    }
    return arr[number];
    // write code here
}
module.exports = {
    rectCover : rectCover
};

解题思路

1. 先上图：
   　　21的大矩形和2n的小矩形：

1.png

2. 第一次覆盖有两种情况：
   　　横着覆盖：

2.png

竖着覆盖：

3.png

3. 由此可得：

   当第一次横着覆盖时，覆盖方法为f(n-2);
   当第一次竖着覆盖时，覆盖方法为f(n-1);
   因此f(n)=f(n-1)+f(n-2);
   当n=1时，只有1种覆盖方法，当n=2时，有2种覆盖方法。
   此题最终得出的仍然是一个斐波那契数列。
   n=1, f(n)=1
   n=2, f(n)=2
   n>2,且为整数, f(n)=f(n-1)+f(n-2)