《剑指offer》— JavaScript（10）矩形覆盖

矩形覆盖

题目描述

我们可以用（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)