【剑指offer】python实现矩形覆盖
题目描述
我们可以用2 * 1 的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2 * 1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
思路
这是一道递归题，首先我们可以列举n=1,2,3,4时的情形观察一下规律（显然n=0时，为0）
可以明显看到f(n)=f(n-1)+f(n-2)
AC代码
class Solution:
def rectCover(self, number):
# write code here
if number == 0:
return 0
tempArray = [1,2]
if number >= 3:
for i in range(3,number+1):
tempArray[(i+1)%2] = tempArray[0] + tempArray[1]
return tempArray[(number+1)%2]