10-矩形覆盖-动态规划

题目描述

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

题目分析

当然也可以逆向思维

应为可以横着放或竖着放，多以f(n)可以是2(n-1)的矩形加一个竖着放的21的矩形或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==1) return 1;
    if(number==2) return 2;
    let last = 1;
    let nextLast =2;
    let res = 0;
    while(number>2){
        res = last + nextLast;
        last = nextLast;
        nextLast = res;
        number--
    }
    return res;
    
}