本文共 573 字，大约阅读时间需要 1 分钟。

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

比如n=3时，2x3的矩形块有3种覆盖方法：

示例: 输入：4 ==> 返回：5 输入：5 ==> 返回：8

【解题思路】

我们先把2x5的覆盖方法记为f(5)。用第一个1x2小矩阵覆盖大矩形的最左边时有两个选择，竖着放或者横着放。 当竖着放的时候，右边还剩下2x4的区域，这种情况下的覆盖方法记为f(4)。 接下来考虑横着放的情况。当1x2的小矩形横着放在左上角的时候，左下角必须横着放一个1x2的小矩形，而在右边还剩下2x6的区域，这种情况下的覆盖方法记为f(3)。因此f(5)=f(4)+f(3)。 此时我们可以看出，这仍然是斐波那契数列。

class Solution:    def rectCover(self, number):        if number<=3:            return number        a,b,sums=1,2,0        for _ in range(3,number+1):            sums = a+b            a = b            b = sums        return sums

转载地址：http://lfjii.baihongyu.com/