JZ10 -矩形覆盖问题(JS)

    技术2022-07-10  201


    题目描述:矩形覆盖问题


    我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2n的大矩形,总共有多少种方法? 比如n=3时,23的矩形块有3种覆盖方法:


    题目解析:


    当n = n,可以分为两种情况来讨论,

    (1)第一次用一个21的小矩形作为第一个格,那么剩下2(n-1)个矩形等待填充。

    (2)第一次用一个12的小矩形作为第一个填充的矩形,下面的那个小矩形是必然要进行填充的,那么剩下2(n-2)个小矩形等待填充,所以n = n的情况总的方法为两种情况相加。 return f(n) = f(n-1) + f(n-2)。

    function rectCover(number) { // write code here if(number <= 2){ return number; } var before = 1; var after = 2; for(i=3; i<=number; i++){ after = before + after; before = after - before; } return after; }
    Processed: 0.011, SQL: 9