剑指offer（10）矩形覆盖

2022-04-07 01:34:28

题目描述

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

题目分析

当然也可以逆向思维

应为可以横着放或竖着放，多以f(n)可以是2*(n-1)的矩形加一个竖着放的2*1的矩形或2*(n-2)的矩形加2横着放的，即f(n)=f(n-1)+f(n-2)

当到了最后，f(1)=1,f(2)=2

代码

function rectCover(number) {

  // write code here

  if (number === 0) return 0;

  let f = 1,

    g = 2;

  while (--number) {

    g += f;

    f = g - f;

  }

  return f;

}