首页 > 其他 > 详细

剑指Offer-10矩形覆盖

时间:2020-04-03 09:33:28      阅读:60      评论:0      收藏:0      [点我收藏+]

题目连接

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

题目思路
递推公式: f(n)=f(n-1)+f(n-2)(n>2) f(0)=0,f(1)=1,f(2)=2

Python代码

  • 使用递归,运行时间太长
class Solution:
    def rectCover(self, number):
        assert number >= 0, "error input!"
        if number <= 2:
            return number
        else:
            return self.rectCover(number - 1) + self.rectCover(number - 2)

技术分享图片

  • 使用向前传播循环计算
class Solution:
    def rectCover(self, number):
        assert number >= 0, "error input!"
        if number <= 2:
            return number
        else:
            a = 1
            b = 2
            result = 0
            for i in range(3, number + 1):
                result = a + b
                a = b
                b = result
            return result

技术分享图片

  • 利用数组缓存,减少重复计算, 增加了内存,提高了运行速度
class Solution:
    def __init__(self):
        self.result = []
        self.result.append(0)
        self.result.append(1)
        self.result.append(2)

    def rectCover(self, number):
        assert number >= 0, "error input!"
        if number >= len(self.result):
            for i in range(len(self.result), number + 1):
                self.result.append(self.result[i - 1] + self.result[i - 2])
        return self.result[number]

技术分享图片

剑指Offer-10矩形覆盖

原文:https://www.cnblogs.com/nrocky/p/12624118.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!