题目链接：http://poj.org/problem?id=2411
题意：
给你一个n*m的网格 (1<=n,m<=11) ，往里面铺1*2或2*1的砖块，问你铺完这个网格有多少种不同的方法。
题解：
表示状态：
dp[state][i] = num of ways at ith row
（1）当前铺到了第i行
（2）在铺第i行之前，第i行已经被占的格子状态为state
如何转移：
对于当前第i行的第j列处，有三种情况：
（1）竖着铺。i+1行的第j个位置会被占，在这一行占用了一个宽度，接下来该在第j+1列铺。
（2）横着铺。对i+1行没有影响，在这一行占用了两个宽度，接下来该在j+2列铺。
（3）已经被占。只能不铺，对i+1行没有影响，接下来该在第j+1列铺。
所以在求dp之前先暴搜出在一行上的每个状态state铺完之后下一行的状态，存到vector中。
转移：枚举每一行i，当前行的state，以及当前state能够转移的状态nex。
dp[nex][i+1] += dp[state][i]
AC Code：
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#define MAX_N 15
#define MAX_S (1<<12) using namespace std; int n,m;
long long dp[MAX_S][MAX_N];
vector<int> shift[MAX_S]; void dfs(int col,int state,int nex)
{
if(col==m)
{
shift[state].push_back(nex);
return;
}
if((state>>col)&)
{
dfs(col+,state,nex);
return;
}
dfs(col+,state,nex|(<<col));
if(col+<m && !((state>>(col+))&)) dfs(col+,state,nex);
} int main()
{
while(cin>>n>>m)
{
if(n== && m==) break;
for(int state=;state<(<<m);state++)
{
shift[state].clear();
}
for(int state=;state<(<<m);state++)
{
dfs(,state,);
}
memset(dp,,sizeof(dp));
dp[][]=;
for(int i=;i<n;i++)
{
for(int state=;state<(<<m);state++)
{
if(dp[state][i])
{
for(int j=;j<shift[state].size();j++)
{
int nex=shift[state][j];
dp[nex][i+]+=dp[state][i];
}
}
}
}
cout<<dp[][n]<<endl;
}
}