剑指Offer(十):矩形覆盖

  • 2
  • 282 °C
  • A+
所属分类:剑指Offer
摘要

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

剑指Offer(十):矩形覆盖

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台:牛客网

书籍下载:共享资源

二、题目

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

1、思路

以2x8的矩形为例。示意图如下:

剑指Offer(十):矩形覆盖

我们先把2x8的覆盖方法记为f(8)。用第一个1x2小矩阵覆盖大矩形的最左边时有两个选择,竖着放或者横着放。当竖着放的时候,右边还剩下2x7的区域,这种情况下的覆盖方法记为f(7)。接下来考虑横着放的情况。当1x2的小矩形横着放在左上角的时候,左下角和横着放一个1x2的小矩形,而在右边还剩下2x6的区域,这种情况下的覆盖方法记为f(6)。因此f(8)=f(7)+f(6)。此时我们可以看出,这仍然是斐波那契数列

2、代码

C++:

Python2.7:

Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论:2   其中:访客  1   博主  1

    • avatar Song 来自天朝的朋友 谷歌浏览器 Windows 10 辽宁省沈阳市 东北大学四舍(女生) 2

      是最好不要用递归吗,用C++递归可以通过,用Python就不行

        • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 10 北京市 联通

          @Song 嗯,最好不要用,时间复杂度高,用循环就行。