[剑指Offer]矩形覆盖

本文首发于我的个人博客Suixin’s Blog
原文: https://suixinblog.cn/2019/03/target-offer-rectangle-cover.html　　作者: Suixin

题目描述

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

解题思路

本质上，覆盖的方法数为斐波那契数列。画图可得，2*1的小矩形横着或者竖着放置，是两种互斥的情况，即

图解

代码

Python(2.7.3)

# -*- coding:utf-8 -*-
class Solution:
    def rectCover(self, number):
        # write code here
        if number < 0:
            return
        elif number == 0:
            return 0
        a, b = 1, 1
        for _ in range(number):
            a, b = b, a + b
        return a

运行时间：30ms
占用内存：5860k