题目描述
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?
题目思路
递推公式: f(n)=f(n-1)+f(n-2)(n>2) f(0)=0,f(1)=1,f(2)=2
Python代码
class Solution:
def rectCover(self, number):
assert number >= 0, "error input!"
if number <= 2:
return number
else:
return self.rectCover(number - 1) + self.rectCover(number - 2)
class Solution:
def rectCover(self, number):
assert number >= 0, "error input!"
if number <= 2:
return number
else:
a = 1
b = 2
result = 0
for i in range(3, number + 1):
result = a + b
a = b
b = result
return result
class Solution:
def __init__(self):
self.result = []
self.result.append(0)
self.result.append(1)
self.result.append(2)
def rectCover(self, number):
assert number >= 0, "error input!"
if number >= len(self.result):
for i in range(len(self.result), number + 1):
self.result.append(self.result[i - 1] + self.result[i - 2])
return self.result[number]
原文:https://www.cnblogs.com/nrocky/p/12624118.html