我的刷题日记（4）

2018年8月3日

矩形覆盖

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

假设n块矩形有F(n)种方法能铺满这个2*n的矩形，那么完成最后一步搭建可能是横着放，也有可能是竖着放。如下图， （1）横着放，那么剩下的未知放法的还剩下n-1块，那么就是F(n-1)种方法。 （2）竖着放，那么旁边那块也必须得竖着放，那么剩下的未知方法的就是n-2块即F(n-2)种方法。 所以 F(n) = F(n-1) + F(n-2) 这是什么？这不就是斐波拉契数列吗…那就简单了

运行时间：16ms 占用内存：6060k

function rectCover(n){ if(n <= 2){ return n; } let prepreNum = 1; let preNum = 2; let result; for(let i = 3;i <= n;i++){ result = prepreNum + preNum; prepreNum = preNum; preNum = result; } return preNum; }