剑指—JZ10矩形覆盖
题目描述
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?
比如n=3时,2*3的矩形块有3种覆盖方法:
解题思路
记忆化递归
这了可以以长来做判断,这里长就是n,每次填充要么竖着填充即填充1,要么横着填充即填充2,所以和斐波那契数列有点像
# -*- coding:utf-8 -*- class Solution: def __init__(self): self._dict = {} def rectCover(self, number): # write code here def dfs(n): if n == 0: return 1 if n < 0: return 0 if n in self._dict: return self._dict[n] self._dict[n] = dfs(n - 1) + dfs(n - 2) return self._dict[n] if number == 0: return 0 res = dfs(number) return res S = Solution() print(S.rectCover(3))