题目原题可以看POJ2411，大意是给出m*n的矩形，要用2*1的矩形将它铺满（不能讲一个矩形铺在另外一个上面），求方案数，并且只要不是完全相同的就算不同的方案，也就是对称算不同的方案。
F[i][s]表示前i-1行已经填满，并且第i行的状态是s的方案数。
F[i][s]=sum(F[i-1][s’])；
s‘能转移到s。如何根据s来确定s‘呢。这里用一个dfs实现，一位一位去填充s‘。扫描s，如果该位是1，那么s’对应的这位必定是0，如果该位是0，那么要分情况讨论：
如果该位的后面一位也是0，那么s’对应的这位和s‘对应的后面一位可能都是1，也有可能是00，
Mondriaan的梦（状态压缩dp）,布布扣,bubuko.com
原文：http://www.cnblogs.com/vb4896/p/3900160.html