广场铺砖问题——状态压缩动态规划

题目大意：有一个长H，宽W的广场，要铺满2x1规格的砖块，不允许砖块重叠，求一共有多少种方案？（H，W均不超过11）

题目的数据范围相当小，不过还没有小到可以用DFS解决的规模（DFS每次只能把方案数增加1,而W=10,H=11的方案数为已经超过10^11了）。

注意到题目的砖块只有两种摆放方式：横着或者竖着。加之广场边长小于11,因此考虑用状态压缩动态规划（不熟悉这个名词的读者可以参考这篇文章）。用一个整数的每一位对应一个横排每个位置是否有砖块。
那么，转移方程就是：F[i][S] = Sigma{F[i-1][S']} (S'可以转移到S)
边界是：F[1][0] = 1

现在要做的就是找出各个状态之间的转移关系。这时DFS就派上用场了，我们只需考虑两行，枚举第一行的状态i，根据i搜索得到第二行能达到的状态j，把adj[i][j]赋值为1.具体实现请看后面的程序。

获得矩阵adj后，就可以用三个for逐行求出F[i][S]的方案了，最后输出F[H+1][0]（或者F[H][(1 << W) - 1]）.

此外，由于砖块的面积是2，如果广场面积是奇数，显然是无解的，可以直接输出0.

C语言: 高亮代码由发芽网提供

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>

long long f[13][2050];
_Bool adj[2050][2050];    //所有可能的转移
int W,H;

void dfs(int from,int step,int to)
{
   if(step == W)
   {
       adj[from][to] = 1;
       return;
   }
   if(((1 << step) & from) != 0)    //已经放过，考察下一个
       dfs(from,step + 1,to);
   else
   {
       if((step <= W - 2) && ((1 << (step + 1)) & from) == 0)    //两块都是空的，可以横放
               dfs(from,step + 2,to);
       dfs(from,step + 1,to | (1 << step));   //竖着放
   }
}

int main()
{
   freopen("floor.in","r",stdin);
   freopen("floor.out","w",stdout);
   scanf("%d%d",&W,&H);
   if((W * H) % 2 == 1)    //无解情况
   {
       printf("0\n");
       fclose(stdout);
       exit(0);
   }
   int max = 1 << W;
   int i,j,k;
   for(i = 0;i < max;i ++)    //DFS构建矩阵
       dfs(i,0,0);
   f[0][0] = 1;
   for(i = 0;i < H;i ++)
       for(j = 0;j < max;j ++)
           for(k = 0;k < max;k ++)
               if(adj[j][k])    f[i + 1][k] += f[i][j];
   printf("%I64d\n",f[H][0]);
   fclose(stdout);
   return 0;
}