面试题10.4（矩形覆盖）面试题10.4：矩形覆盖

题目描述我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
知识点递归，循环
Qiang的思路对于这道题，小矩形是21的，大矩形是2n的，这就意味是每个小矩形可以竖着放，一次性就把2行给占满了，或者横着放，这样肯定相邻行的也得横着放了。换句话说，如果我们在考虑大矩形的第i列时（此时前i-2列都已放满），我们可以看下第i-1列有没有矩形，如果i-1有，那么第i列只能竖着放一个小矩形，如果没有，那么第i列和第i-1列可以合起来横着放两个小矩形（不能竖着放，竖着放和第i-1列有的情况就一样了）。
基于这个思想，我们发现，当大矩形有n列时，总共的方法数为：

好啊，又是个斐波那契数列。那代码直接就出来了。

# -*- coding:utf-8 -*- class Solution: def rectCover(self, number): # write code here f=[1,1] for i in range(2,number+1): a=f[1] f[1]=f[1]+f[0] f[0]=a return f[1] if number!=0 else 0

至于这个题当n为0时返回0完全是出题人这样规定的，实际认为是1也不是不可，毕竟啥都不放本身就是一种方法嘛。