矩形覆盖
题目描述
我们可以用（2*1）的小矩形横着或者竖着去覆盖更大的矩形。请问用n个（2*1）的小矩形无重叠地覆盖一个（2*n）的大矩形，总共有多少种方法？
实现代码
function jumpFloor(number)
{
if (number<0){
return -1;
}else if(number <=2){
return number
}
var arr = [];
arr[0] = 1;
arr[1] = 2;
for(var i = 2; i < number; i++) {
arr[i] = arr[i - 1] + arr[i - 2];
}
return arr[number-1];
思路
1. 先上图：
2*1的大矩形和2*n的小矩形：
图片.png
2. 第一次覆盖有两种情况：
横着覆盖：
图片.png
竖着覆盖：
图片.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)
