本文首发于我的个人博客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
网友评论