我一直在尝试解决this programming problem，但是由于无法解决，我在线找到了一个解决方案。但我真的不明白为什么该解决方案也可以..
任务是以3种方式(完全输入2 * 1个多米诺骨牌)完全地将3 * n(n >= 0，n是唯一输入)矩形计算为。
例如(红线代表多米诺骨牌):
这是我阅读文字时首先在一张纸上绘制的内容，并且看到3 * 2矩形可以具有三种可能的组合，并且如果n为奇数，则解为0，因为没有办法然后填充整个矩形(一块永远不会被多米诺骨牌覆盖)。
所以我以为解决方案就是如果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;
}
为什么这样做？!
最佳答案
令T(n)为可以用3×n磁贴平铺2×1板的方式的数量。同样，让P(n)为可以用3×n磁贴移除一个角落的2×1板的磁贴数量。假设n足够大(>= 4)。
然后考虑如何从左(或右，无所谓)开始平铺。
您可以通过两种方式放置覆盖左上角的图块:垂直或水平。如果垂直放置，则必须将覆盖左下角的瓷砖水平放置，以进行配置
|
==
剩下的
P(n-1)方法可以平铺其余部分。如果将其水平放置，则可以水平或垂直放置覆盖左下角的瓷砖。如果将其垂直放置，则与以前一样，只是处于反射状态；如果将其水平放置，则必须在它们之间水平放置一块瓷砖，==
==
==
剩下一个
3×(n-2)板来平铺。因此T(n) = T(n-2) + 2*P(n-1) (1)
现在，考虑到
3×(n-1)板的一个角已被移除(已经覆盖)(假设左上角)，您可以在其下方垂直放置一个图块，从而得到=
|
并留下一个
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.