剑指offer——矩形覆盖（5）Python实现

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

考点：递归和循环

分析：

当 n=1时，有一种覆盖方法。f(1)=1
当 n=2时，有两种覆盖方法。f(2)=2
当n=3时，分为两种情况：

第一次用一个矩形竖着覆盖（左图蓝色），则剩下共有f(n-1)种方法，即f(2) 种方法；

第一次用一个矩形横着覆盖（右图蓝色），则剩下绿色区域只能有图示一种方法，那么剩下f(n-2)种方法，即f(1) 种方法；

图片文字来自博客。

所以，f(3)=f(3-1)+f(3-2)

最终，f(n)=f(n-1)+f(n-2)。又是斐波那契数列数列的通式。

# -*- coding:utf-8 -*-
class Solution:
    def rectCover(self, number):
        # write code here
        if number < 0:
            return 0
        elif number < 3:
            return number   
        a = 1
        b = 2
        temp = 0
        for i in range (3, number+1): //同理循环的方式进行
            temp = a + b 
            a = b 
            b = temp
        return temp

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

#同理使用递归，显示错误如下
不通过
您的代码已保存
运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。
case通过率为0.00%

剑指offer——矩形覆盖（5）Python实现

浏览过的版块