矩阵覆盖
题目描述
我们可以用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
};
解题思路
- 先上图：
21的大矩形和2n的小矩形：
1.png
- 第一次覆盖有两种情况：
横着覆盖：
2.png
竖着覆盖：
3.png
-
由此可得：
当第一次横着覆盖时，覆盖方法为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)
