10.矩形覆盖

题目

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

比如n=3时，2 * 3的矩形块有3种覆盖方法： ()[../images/offer10.png]

详解

每次使用两个变量a，b来计算下一个数的值sum，然后a，b，sum分别是斐波那契数列中的三个数，那么就令a=b，b=sum，这样a和b就往下移动了一个位置，再计算sum就是第4个数了，重复这个过程即可。

target = 1时，1种
target = 2时，2种
target = 3时，3种
target = 4时，5种
target = n时，分两步考虑：

• 第一次摆放2* 1的小矩形，则摆放方法总共为f(target-1);
• 第一次摆放1* 2的小矩形，则摆放方法总共为f(target-2);

这就是斐波那契数列啊。

JS实现

function rectCover(number) {
  // write code here
  if (number === 1) {
    return 1;
  }
  if (number === 2) {
    return 2;
  }

  let a = 1,
    b = 2,
    sum = 0;
  for (let i = 3; i <= number; i++) {
    sum = a + b;
    a = b;
    b = sum;
  }
  return sum;
}