《剑指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的小矩形：

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

　　横着覆盖：

　　竖着覆盖：

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)