使用Python计算3 x n方格内用2 x 1骨牌填充的方法数量

更多Python相关文章，请阅读：Python 教程

问题描述

给定一个3 x n的方格，现在需要我们用2 x 1的骨牌将其填满，求有多少种方法可以填充。

问题分析

首先我们可以得到一下观察结果：

当n = 1时，只能用两个小方格来填充，无解；

当n = 2时，只有一种方法，用两个小方格组成一块2 x 1的大方格并填入；

当n = 3时，总方法数为2，分别是：

将3 x 2的方格填满，剩余一个1 x 1的小方格处于左上角；
将3 x 2的方格填满，剩下的1 x 1的小方格处于右上角。

我们发现，对于n > 2的情况，我们可以将3 x n的方格划分为两部分：

一个2 x n的方格；
两个3 x n-2的方格。

现在考虑如何将骨牌放入其中。我们可以分三种情况来考虑。

情况一

将一块2 x 1的大方格垂直放入2 x n的方格中，如下所示：

|-------|   |-------|   |-------|
|o****o |   | ooo o |   | o   o |
|o****o |   | ooo o |   | o   o |
|-------|   | ooo o |   |ooooo o|
            |-------|   |ooooo o|

在这个情况下，我们可以重新定义一个2 x (n-1)的方格，再次进行划分。

情况二

将两块2 x 1的大方格水平放入2 x n的方格中，如下所示：

|-------|   |-------|
|o****o o|   | ooo o |
|o****o o|   |ooooo o|
|-------|   |ooooo o|

在情况二中，我们可以重新定义一个2 x (n-2)的方格，再次划分。

情况三

如果将两块2 x 1的大方格分别放入两个3 x n-2的方格中，我们可以得到两个新的3 x n-2的方格，如下所示：

----------*  *----------

|-----------|   |-----------|
| o  o  ooo o|   |ooooooooo o|
| o  o  ooo o|   |ooooooooo o|
| o  o  ooo o|   |ooooooooo o|
|-----------|   |-----------|

----------*  *----------

|-----------|   |-----------|
| ooo o  o  o|   |o ooooooooo|
| ooo o  o  o|   |o ooooooooo|
| ooo o  o  o|   |o ooooooooo|
|-----------|   |-----------|

在情况三中，我们需要考虑分别放入左右两边的大方格究竟是哪一种情况，也就是说我们需要将情况三再次细分。

现在我们已经能够将问题进行具体化，根据不同情况再次进行划分即可得到计算方法。

推导计算公式

我们令f(n)表示3 x n的方格用2 x 1的骨牌填充的不同方案数。对于两种边角的特殊情况n = 1和n = 2，可以直接得出： $f(1) = 0,f(2) = 1$ 对于n > 2的情况，可以使用上一节中的方法进行递归推导。

情况一

在2 x n的方格中，我们使用一块2 x 1的大方格垂直放置，得到以下图形：

|-------|
|o****o |
|o****o |
|-------|

我们可以将这个方格转化为一个2 x (n-1)的方格，再次进行划分。此时，该方格有两个空位置：

|--|--|
|**| o|
|**| o|
|--|--|

第1个空位置：

插入一个2 x 1的小方格，则剩下的部分需要使用2 x (n-2)的方格填满，方案数为f(n-2)；
插入一个1 x 2的小方格，则必须将其与原来的2 x 1的大方格组成一个2 x 2的大方格，并插入对应位置，剩下的部分需要使用2 x (n-3)的方格填满，方案数为f(n-3)。

第2个空位置同理，这样我们就推导出了情况一的公式：

$f(n) = f(n-1) + f(n-2) + 2\sum\limits_{i=3}^{n}f(n-i)$

情况二

在2 x n的方格中，我们使用两块2 x 1的大方格水平放置，如下所示：

|--------|
|o****o o|
|o****o o|
|--------|

此时，我们可以定义一个2 x (n-2)的方格，再次进行划分。这个方格有一个空位，插入一个2 x 1的小方格，那么剩下的部分需要使用2 x (n-4)的方格填满，方案数为f(n-4)。还有一种情况，需要将空位插入一个1 x 2的小方格，那么必须将其与原来的2 x 1的大方格组成一个2 x 2的大方格，并插入对应位置，剩下的部分需要使用2 x (n-5)的方格填满，方案数为f(n-5)。最终的公式为：

$f(n) = f(n-2) + 2\sum\limits_{i=4}^{n}f(n-i)$

情况三

对于情况三，需要进一步细分：

将一个2 x 1的大方格插入到左边，另一个插入到右边；
将一个2 x 1的大方格插入到左边，再将一个1 x 2的小方格插入到右边；
将一个1 x 2的小方格插入到左边，再将一个2 x 1的大方格插入到右边；
将一个1 x 2的小方格插入到左边，另一个插入到右边。

对于第一种情况，我们将左右两部分分别定义为一个3 x (n-2)的方格，再次进行划分。对于第二种情况，我们需要使用3 x (n-3)的方格填满后，再在左边使用一个2 x 1的大方格，右边使用一个2 x 2的大方格；对于第三种情况，我们需要使用3 x (n-3)的方格填满左边，再在右边使用一个2 x 1的大方格；对于第四种情况，同样将左右两边分别定义为3 x (n-2)的方格，继续进行划分。

最终的推导公式为：

$f(n) = 2f(n-2) + f(n-4) + 2\sum\limits_{i=5}^{n}f(n-i)$

Python实现

根据上述推导公式，我们可以使用递归 + 动态规划的方式进行求解。

def calc_methods(n, memo):
    if n == 1:
        return 0
    elif n == 2:
        return 1
    elif memo[n] is not None:
        return memo[n]
    else:
        memo[n] = calc_methods(n-1, memo) + calc_methods(n-2, memo)
        for i in range(3, n+1):
            memo[n] += 2 * calc_methods(n-i, memo)
        if n % 2 == 0:
            memo[n] += 2
        else:
            memo[n] += calc_methods((n-1)//2, memo) + calc_methods((n+1)//2, memo)
        return memo[n]

n = int(input("请输入一个正整数n："))
memo = [None for _ in range(n+1)]
print("共有{}种方法可以填满3 x {}的方格".format(calc_methods(n, memo), n))

在上述代码中，我们使用了一个memo数组来记录每个n对应的方法数，避免重复计算。另外，由于第三种情况需要进行奇偶性判断，因此我们使用了三元运算符对奇偶情况进行判断。这样，我们就可以在O(n)的时间复杂度下解决该问题。