剑指Offer编程题-矩形覆盖 | 我的个人生活记录

题目：矩形覆盖

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

解题思路

2*1的小矩阵：

当第一个小矩阵竖着放时：

剩下的(n-1)个矩阵的放法有F(n-1)种

当第一个小矩阵横着放时，第二个也只能横着放：

剩下(n-2)个小矩阵的放法有F(n-2)种，所有总的放法：F(n) = F(n-1) + F(n-2)种，也是一个斐波那契数列。

实现

python

# -*- coding:utf-8 -*-
class Solution:
    def rectCover(self, number):
        # write code here
        if number <= 2:
            return number
        a = 1
        b = 2
        while number > 2:
            b = a + b
            a = b - a
            number -= 1
        return b