In how many ways can you tile a 3xn rectangle with 2x1 dominoes? Here is a sample tiling of a 3x12 rectangle.

http://acm.hdu.edu.cn/showproblem.php?pid=1143

Input consists of several test cases followed by a line containing -1. Each test case is a line containing an integer 0 ≤ n ≤ 30.

For each test case, output one integer number giving the number of possible tilings.

思路

递推真的是头疼。

​ 首先应该是可以很轻松的知道两点和不太容易知道一点。

​ 其一是奇数列的结果都为0,因为奇数列是填不满的。

​ 其二是dp[2]=3,2X3时可以有3种情况。

​ 其三,不太容易找到的规律,除了2有三种外,之后的偶数列不进行拆分都只有2种。

​ 面对4X3的情况,首先可以分割成两个2X3,即dp[2]*dp[2]=9,其次4X3整体考虑有两种情况,所以dp[4]=9+2=11。

​ 面对6X3的情况,首先可以分割成三个2X3,即dp[2]^3 = 27,其次可以分割成一个4X3加一个2X3(可以交换位置,所以有两种),得232=12,最后对6X3整体考虑有两种,所以dp[6]=27+12+2=41

​ 推到这里,我们大致找到规律了,但是没有递推转化式,但是只要我们稍微转换一下思维就可以得到下面的正确解法了。

​ 用递推的思想来解决的话,可以这样考虑问题。

​ 设dp[n]表示nX3的方块,那么分以下几步考虑:

​ 1. 整体不进行划分(指的是不考虑子问题),前面提到了第三点,共2 种情况,这里我们换一个角度相就是将前n列方块和最后0列方块划分考虑,即2*dp[0];

​ 2. 将最后面两列和前面的n-2列分开考虑,此时就是一个子问题:dp[2]dp[n-2] = 3dp[n-2];

​ 3. 继续将最后面的四列和前面的n-4分开考虑,此时就是子问题:dp[4]dp[n-4] = 2dp[n-4];

​ 4. 继续将最后面的六列和前面的n-6分开考虑,此时就是子问题:dp[6]dp[n-6] = 2dp[n-6];

​ ……

​ 若干次划分后,我们得到dp[n] = 3dp[n-2] + 2(dp[n-4]+dp[n-6]+……+dp[0]);

​ 而进行一下简单的推导可得,dp[n-2] = 3dp[n-4] + 2(dp[n-6]+……+dp[0]);

​ 将两式相减就可以得到 dp[n] = 4*dp[n-2] - dp[n-4];

​ 其中dp[0]=1;是一个比较容易弄错的点

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<cstdio>  
#include<cstring>
const int maxn=31+10;

int dp[maxn],n;


int main()
{
dp[0]=1;
dp[2]=3;
for(int i=4;i<=32;i++)
dp[i]=4*dp[i-2]-dp[i-4];
while(~scanf("%d",&n)&&n!=-1)
{
if(n%2) printf("0\n");
else printf("%d\n",dp[n]);
}
return 0;
}