题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1400
题目意思：给出一个h * w的 大 矩形，需要用 1 * 2 的砖块去填充这个大矩形，问填充的方案数是多少。
这题参考这里的：
http://www.informatik.uni-ulm.de/acm/Locals/2000/solution/dream.c
把每一列的方格压缩为二进制编码，搜索上一列到当前列的状态转化是否能够成功。对于每一个位置，有3种放置方法：竖直、水平、不放
对每个方格，1表示填充砖块，0表示没有填充砖块。将一层的状态存放在一个二进制数中。
1、利用dfs，计算第一层的填充状态
2、从第 1 层向第 n 层，利用DP 递推结果。
变量from 和 to 的最大值，是宽为W的方格中都填充1，即（1<<W）-1，或者2^W-1
初始时，假设第 0 层都填充1，只有一种情况。
使用数组dp 表示每一层的递推关系，递推公式：
令：from[j] = state[j] [0]， to[j] = state[j] [1]，0 ≤ j < nstate
则dp[i+1] [to[j]] = ∑ dp[i] [from[j]]， 0 ≤ j < nstate， 0 ≤ i < H
0 ≤ j < nstate
最近都是抄人代码的节奏= =，哎~~~~，继续努力吧！！！
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 using namespace std; 6 7 double dp[13][2100]; // 存放各层的递推结果(当宽为11时，2^11-1 = 2047，开2100即可） 8 int state[14000][2]; // 保存状态转化的结果 9 int H, W, nstate; 10 11 // n: 当前从左往右数第n个方格，from：前n个方格在这一层编码, to：下一层的编码 12 // from 和 to的二进制长度与大长方形的宽度W是一致的 13 void dfs(int n, int from, int to) 14 { 15 if (n > W) 16 return; 17 // 整个宽度W填充完毕 18 if (n == W) 19 { 20 // 保存当前的状态转化 21 state[nstate][0] = from; 22 state[nstate++][1] = to; 23 return; 24 } 25 // 放置砖块的3种状态 26 // 水平放置砖块 27 dfs(n+2, (from<<2)+3, (to<<2)+3); // 这个地方的+3， 后面的+1 不知道它想干嘛。希望有能之士可以指点指点 28 // 竖直放置砖块 29 dfs(n+1, (from<<1)+1, to<<1); 30 // 不放置 31 dfs(n+1, from<<1, (to<<1)+1); 32 } 33 34 void DP() 35 { 36 memset(dp, 0, sizeof(dp)); 37 // 第0层都填充1，只有一种情况 38 dp[0][(1<<W)-1] = 1; 39 for (int i = 0; i < H; i++) 40 { 41 for (int j = 0; j < nstate; j++) 42 dp[i+1][state[j][1]] += dp[i][state[j][0]]; 43 } 44 } 45 46 int main() 47 { 48 while (scanf("%d%d", &H, &W) != EOF && (H+W)) 49 { 50 if (H < W) 51 swap(H, W); 52 nstate = 0; 53 dfs(0, 0, 0); 54 DP(); 55 printf("%.0f ", dp[H][(1<<W)-1]); 56 } 57 }