c++ - 用 2 x 1 多米诺骨牌填充 3xN 瓷砖的方法数 (SPOJ : M3TILE)

Question

我一直在努力解决 this programming problem ，但由于我想不通，所以我在网上找到了解决方案。但我真的不明白为什么该解决方案也有效..

任务是计算一个 3*n(n >= 0，n 是唯一的输入)矩形可以用多少种方法完全填充 2* 1 block 多米诺骨牌。

例如(红线代表多米诺骨牌):

这是我在看课文时首​​先在纸上画的，我看到一个 3*2 的矩形可以有三种可能的组合，如果 n 是奇数，则解为 0，因为有没有办法填满整个矩形(一 block 总是被多米诺骨牌覆盖)。

所以我认为解决方案很简单，如果 n 为偶数，则为 3^n，如果 n 为奇数，则为 0。事实证明，我错了。

我在这里找到了一个相对简单的解决方案:

#include <iostream>

using namespace std;

int main()
{
    int arr[31];

    arr[0]=1;
    arr[1]=0;
    arr[2]=3;
    arr[3]=0;

    for(int i = 4; i < 31; i++) {
        arr[i] = arr[i-2] * 4 - arr[i-4]; //this is the only line i don't get
    }

    int n;

    while(1) {
        cin >> n;

        if(n == -1) {
            break;
        }

        cout << arr[n] << endl;
    }

    return 0;
}

为什么会这样？!

Answer 1

设 T(n) 是用 2×1 瓷砖拼贴 3×n 棋盘的方法数。此外，设 P(n) 是用 2×1 瓷砖移除一个角的 3×n 板的拼贴方式的数量.假设 n 足够大 (>= 4)。

然后考虑如何从左侧(或右侧，无所谓)开始平铺。

您可以通过垂直或水平两种方式放置覆盖左上角的图 block 。如果竖着放，覆盖左下角的tile一定要横着放，给个配置

|
==

剩下 P(n-1) 种方式来平铺剩余部分。如果水平放置，则可以水平或垂直放置覆盖左下角的瓷砖。如果竖着放，就是和之前一样的情况，只是反射(reflect)而已，如果横着放，就必须在它们之间横着放一个tile，

==
==
==

留给您一 block 3×(n-2) 板来平铺。因此

T(n) = T(n-2) + 2*P(n-1)              (1)

现在，考虑到 3×(n-1) 板有一个被移除(已经被覆盖)的角(假设左上角)，您可以在其下方垂直放置一 block 瓷砖，给出

=
|

然后给你留下一个 3×(n-2) 的棋盘来拼贴，或者你可以在它下面水平放置两个拼贴，给出

=
==
==

然后你别无选择，只能在顶部水平放置另一个瓷砖，留下你

===
==
==

用 3×(n-3) 板减去一个角，

P(n-1) = T(n-2) + P(n-3)

加起来，

T(n) = T(n-2) + 2*(T(n-2) + P(n-3))
     = 3*T(n-2) + 2*P(n-3)                            (2)

但是，使用 (1) 和 n-2 代替 n，我们看到了

T(n-2) = T(n-4) + 2*P(n-3)

或

2*P(n-3) = T(n-2) - T(n-4)

将其插入 (2) 产生重复

T(n) = 4*T(n-2) - T(n-4)

q.e.d.