铺砖问题是组合数学中的一类经典问题，是利用递推关系解决实际问题的一个典型案例。

即是针对一个特定的道路，比如1*N的道路，有两种砖块来铺设，一种是方砖1*1的，一种是长砖1*2的，用这两种砖，有什么铺设方案？

解决方案，就是采取递推关系。假设方案数为，以最后一块砖的种类为分析对象，如果是方砖，则方案数为；如果是长砖，则方案数为。那么总体的方案数。

求得递推关系以后，根据齐次线性方程组的特征方程，可以求得铺砖方案数。

以上是最简单的铺砖问题，也是从数学的角度解释什么是铺砖问题以及铺砖问题的求解。

铺砖问题，其实还是一个动态规划的问题，而且是一个状态压缩的动态规划问题。所谓状态压缩型动态规划，就是将不方便转移或数据量极大的状态用01字串来表示，这样就可以方便的转移状态，同时节省了大量的空间。

有一个长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].（即能将第h行铺满的方案数）.

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