题目描述
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
解题思路
本质上，覆盖的方法数为斐波那契数列。画图可得，2*1的小矩形横着或者竖着放置，是两种互斥的情况，即$f(n)=f(n-2)+f(n-1)$
代码
Python(2.7.3)1
2
3
4
5
6
7
8
9
10
11
12# -*- coding:utf-8 -*-
class Solution:
def rectCover(self, number):
# write code here
if number < 0:
return
elif number == 0:
return 0
a, b = 1, 1
for _ in range(number):
a, b = b, a + b
return a运行时间：30ms占用内存：5860k