题目描述
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
思路
依旧是斐波那契数列拓展，从第3个数之后每个数都是前两个数的和
Code
- Python
# -*- coding:utf-8 -*-
mp = {
0:0,
1:1,
2:2,
3:3
}
class Solution:
def rectCover(self, number):
if number not in mp.keys():
mp[number] = self.rectCover(number-1) + self.rectCover(number-2)
return mp[number]
- JavaScript
mp = [0, 1, 2, 3]
function rectCover(number)
{
if (typeof(mp[number]) === 'undefined')
mp[number] = rectCover(number - 1) + rectCover(number - 2)
return mp[number]
}
网友评论