剑指Offer - 10 - 矩形覆盖

题目描述

矩形覆盖

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

思路

依旧是斐波那契数列拓展，从第3个数之后每个数都是前两个数的和

Code

• Python

# -*- coding:utf-8 -*-
mp = {
  0:0,
  1:1,
  2:2,
  3:3
}
class Solution:
    def rectCover(self, number):
      if number not in mp.keys():
        mp[number] = self.rectCover(number-1) + self.rectCover(number-2)
      return mp[number]

• JavaScript

mp = [0, 1, 2, 3]
function rectCover(number)
{
  if (typeof(mp[number]) === 'undefined')
    mp[number] = rectCover(number - 1) + rectCover(number - 2)
  return mp[number]
}