题解 | #矩形覆盖#

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

比如n=3时，23的矩形块有3种不同的覆盖方法(从同一个方向看)：*

• 找规律可以得出是斐波那契数列，或者想象先把2X8的覆盖方法记为f(8)，用1X2的小矩形去覆盖时，有两种选择：横着放或者竖着放。当竖着放时，右边还剩下2X7的区域。很明显这种情况下覆盖方法为f(7)。当横着放时，1X2的矩形放在左上角，其下方区域只能也横着放一个矩形，此时右边区域值剩下2X6的区域，这种情况下覆盖方法为f(6)。所以可以得到：f(8)=f(7)+f(6)，不难看出这仍然是斐波那契数列。

class Solution:
    def rectCover(self, number):
        # write code here
        if number < 3:
            return number
        a, b = 1, 2
        for i in range(number - 2):
            b = a + b
            a = b - a
        return b