剑指10-矩形覆盖

Posted on | In |

题目描述

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

  • 按第一个小矩形靠近一端的摆放方式，可以分为互斥且互补的两个空间：
    • 横放，有F(n-2)种方法
    • 竖放，有F(n-1)种方法
  • 因此有F(n) = F(n-1)+F(n-2)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def rectCover(self, number):
        # write code here
        if number <= 0:
            return 0
        if number == 1:
            return 1
        if number == 2:
            return 2
        
        # 教训：能用循环就不要用递归，防止栈溢出
        a, b = 1, 2
        for n in range(3, number+1):
            a, b = b, a + b
        return b