10 矩形覆盖

题目描述

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

示例：

输入: 1, 输出: 1  (竖放)
输入: 2, 输出: 2  (横放两个, 竖放两个)
输入: 3, 输出: 3
输入: 4, 输出: 5

解题思路

核心思想：这实际上是跳台阶问题的变种。考虑最左边一个小矩形的放法：

1. 竖放：剩下是 2*(n-1) 的矩形，有 f(n-1) 种方法
2. 横放：必须两个一起横放，剩下是 2*(n-2) 的矩形，有 f(n-2) 种方法

递推公式：

• f(0) = 1
• f(1) = 1
• f(n) = f(n-1) + f(n-2), n >= 2

这也是斐波那契数列！

时间复杂度：O(n) 空间复杂度：O(1)

Python 实现

def rect_cover(n):
    """
    矩形覆盖问题

    Args:
        n: 2*1小矩形的数量

    Returns:
        int: 覆盖方法数
    """
    if n <= 1:
        return 1

    a, b = 1, 1
    for _ in range(2, n + 1):
        a, b = b, a + b

    return b


# 动态规划版本
def rect_cover_dp(n):
    """
    动态规划版本
    """
    if n <= 1:
        return 1

    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]


# 测试代码
if __name__ == "__main__":
    for i in range(1, 11):
        print(f"覆盖2*{i}矩形: {rect_cover(i)}种方法")

# 输出:
# 覆盖2*1矩形: 1种方法
# 覆盖2*2矩形: 2种方法
# 覆盖2*3矩形: 3种方法
# 覆盖2*4矩形: 5种方法
# 覆盖2*5矩形: 8种方法
# 覆盖2*6矩形: 13种方法
# 覆盖2*7矩形: 21种方法
# 覆盖2*8矩形: 34种方法
# 覆盖2*9矩形: 55种方法
# 覆盖2*10矩形: 89种方法

图解

矩形覆盖分析:
覆盖2*n的矩形，最左边有两种选择:

1. 竖放一个2*1小矩形:
   ┌─┐
   │ │ + 2*(n-1)的矩形
   └─┘

2. 横放两个2*1小矩形:
   ┌─┬─┐
   │ │ │ + 2*(n-2)的矩形
   └─┴─┘

因此: f(n) = f(n-1) + f(n-2)

具体例子:
n=1: ┌─┐  (1种)
      └─┘

n=2: ┌─┐   ┌─┬─┐  (2种)
      └─┘   └─┴─┘

n=3: 有3种方法
     1) 三个竖放
     2) 左边竖放 + 右边两个横放
     3) 左边两个横放 + 右边竖放

结论: f(n) = Fibonacci(n)