矩形覆盖

题目描述

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

分析：

当n==0时return0

n==1时只有一种 return1

当n==2时有两种 return2

重点来了，n==3时 f(3)=f(2)+f(1)

 1 class Solution:
 2     def rectCover(self, number):
 3         # write code here
 4         if number == 0:
 5             return 0
 6         if number == 1:
 7             return 1
 8         if number == 2:
 9             return 2
10         a,b=1,2
11         for i in range(3,number+1):
12             b+=a
13             a=b-a
14         return b

2019-12-01 09:13:42