矩阵放置问题

Question

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

要计算用 n 个 2*1 的小矩形无重叠地覆盖一个 2*n 的大矩形的方法数。

• 当 n=1 时，只有一种方法。
• 当 n=2 时，可以有两种方法，一种是竖着放置两个小矩形，一种是横着放置两个小矩形。
• 当 n>2 时，可以将大矩形分为两部分，最右边一列是用 2*1 的小矩形覆盖的，而前面的 2*(n-1) 部分则有 f(n-1) 种放置方法。最右边两列是横向放置的两个小矩形，而前面的 2*(n-2) 部分则有 f(n-2) 种放置方法。所以，当 n>2 时，有 f(n) = f(n-1) + f(n-2) 种放置方法。

通过递推公式，可以用动态规划的方式计算出 f(n) 。

下面是用 Python 实现的代码：

def cover_rectange(n):
    if n <= 0:
        return 0
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

其中， dp 是一个数组，用来保存计算出的结果。 dp[i] 表示覆盖 2*i 矩形的方法数。

通过上述代码，可以计算出用 n 个 2*1 的小矩形无重叠地覆盖一个 2*n 的大矩形的方法数。