鉴于多次遇到铺砖问题，因此目前遇到对此类问题进行总结：
铺砖问题主要分类：
1.简单的一维铺砖问题
2.二维铺砖问题
2*1的砖是否可以铺满N*M的地面
3.二维铺砖铺满有多少种方法
a.2*1的砖铺满2*M的地面有多少种方法？
b. 2*1的砖铺满N*M的地面有多少种方法？
【问题描述】 有一长度为N(1<=Ｎ<=10)的地板，给定两种不同瓷砖：一种长度为1，另一种长度为2，数目不限。要将这个长度为N的地板铺满，一共有多少种不同的铺法？(蓝桥杯算法训练试题)
【解题思路】
一道简单的递推或者说是DP的题目
N = 1时，只有一种方法 一块长为1的砖
N = 2时，两种方法 两块长为1的砖，一块长为2的砖
N = 3时，三种方法 三块长为1的砖，先一块长为1的砖，后一块长为2的砖,先一块长为2的砖，后一块长为1的砖。
以N=3举例，我们可以这样看
a.先铺好了一块1格的地面，那么再铺一块长为2的砖就可以达到3格
b.先铺好了一块2格的地面，那么再铺一块长为1的砖就可以达到3格
即第i格地面的铺设方式为 第i-1和第i-2的方式的和。
从上面我们可以逐渐发现递推公式 或 状态转移方程 ：dp[i] = dp[i-1]+d。p[i-2];
【代码】
#include <bits/stdc++.h> using namespace std; int dp[50]; int main() { int n; cin >> n; dp[1] = 1; dp[2] = 2; for (int i = 3; i <= 40; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } cout << dp[n]; return 0; }【问题描述】
某年夏天,位于希格玛大厦四层微软亚洲研究院对办公楼的天井进行了一次大 规模的装修.原来的地板铺有 N×M 块正方形瓷砖,这些瓷砖都已经破损老化了,需要予以 更新.装修工人们在前往商店选购新的瓷砖时,发现商店目前只供应长方形的瓷砖,现在的 一块长方形瓷砖相当于原来的两块正方形瓷砖, 工人们拿不定主意该买多少了, 读者朋友们 请帮忙分析一下:能否用 1×2 的瓷砖去覆盖 N×M 的地板呢?
【解题思路】
考虑N，M的奇偶性
A.N*M为奇数，N和M都是奇数,1*2的瓷砖必定不可覆盖
B.N和M至少有一个是偶数，可以设M为偶数（若N为偶数可以交换N和M，保证M为偶），可以知道用1*2的砖铺1*M的砖必定可以铺满，需要M/2块砖。这样N*M就可以转化为重复铺N次1*M的地面的情况
【代码】
#include <bits/stdc++.h> using namespace std; int main() { int n,m; cin>>n>>m; if(n*m%2 == 1){ cout<<"No"; }else{ if(n%2 == 0) swap(n,m); cout<<m/2*n; } return 0; }Ⅰ.2*1的砖铺满2*M的地面，有多少种方式（DP）
【问题描述】
求用1*2的瓷砖覆盖2*M的地板油几种方式?
【解题思路】
1*2的砖有两种铺法——横着或者竖着
A.第一块瓷砖竖着放的时候，问题就可以转化为 用1*2的砖铺设剩下的2*（M-1）地面的方式数
B.第一块瓷砖横着放的时候（必然有另一块横着放的瓷砖在其下面），问题就可以转化为在用1*2的砖铺设剩下的2*（M-2）地面的方式数
由此可得出状态转移方程：dp[i] = dp[i-1] + dp[i-2]；
【代码】
#include <bits/stdc++.h> using namespace std; int dp[50]; int main() { int m; cin >> m; dp[1] = 1; dp[2] = 2; for (int i = 3; i <= 40; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } cout << dp[m]; return 0; }Ⅱ.2*1的砖铺满N*M的地面，有多少种方式（状态压缩+DP）
POJ 2411:Mondriaan's Dream
【题意简述】
有1*2的砖，问铺满N*M的地面需要多少种方式
【解题思路】
解题之前要明确的一些定义或者表示：
1. 考虑N*M的情况：
A.N*M为奇数时，无法铺设
B.N*M为偶数时，可以转化为上边的2*M的问题，可以看作是k*2*M(N = 2*k).故其实仔细分析两行就可以分析出整个地面的铺法。
2.对于所铺砖的表示：
图片来自(https://blog.csdn.net/u013480600/article/details/19569291)
这样表示是为了方便使用状态压缩（状态压缩自行学习），将铺砖的状态用0和1来表示。该矩阵的砖块摆放方法和该矩阵的二进制表示法是一一对应的。
3. 对于两行的是“匹配”的定义：
设当前行所保存的数是cur_，上一行保存的数为pre_，如果cur_和pre_对应的二进制数可以表示把两行的地面铺满，则说其是匹配的。
举个栗子：
对于一个2*5的地面 0 11 11 （十进制15）和 1 11 11 （十进制31）就是合法的，而15和15就是非法的。
砖块摆放有如下的关系: 如果当前位置（i，j）横着放，状态为11，那么上一行（i-1，j）也必须是11，之后我们要考虑（i，j+2） 如果当前位置（i，j）竖着放，状态为1，上一行(i-1,j)为0，之后我们要考虑（i，j+1） 如果当前位置（i，j）不放，那么上一行此位置（i-1，j）为1，当前位置为0，之后我们要考虑（i，j+1）
4.对于DP状态的定义：
dp[i][num]:在第i层为num时（在上述例子中 15和30 就是num）的方式数。
整体思路：
1.每行有三种选择，横着放，竖着放， 不放，如果用1表示横着放和竖着放的第二个，0表示竖着放的第一个和不放，每次都是两行之间的转换， 找出可以互相转换的状态就可以，采用深搜，找到所有pre_和cur_是匹配的二进制状态，将其存到pre[cnt],cur[cnt]这两个数组中。就拿上面例子来讲,可以写pre[0] = 15,cur[0] = 31;
2.第0行可以看作是全部铺成1（看作不需要在代码中写出），那么第0行看作有1种铺砖方法，即dp[0][(1<<m)-1] = 1 ((1<<m)-1代表二进制全为1，想一想)，作为递归基;
3.在循环中依次遍历在pre[cnt]和cur[cnt]保存下来的可以“匹配”二进制状态，状态转移方程：dp[i][cur[j]] += dp[i - 1][pre[j]];
最后要求的结果就是dp[n][(1<<m)-1]
【代码】（一些代码定义会注释）
#include <cstdio> #include <cstring> #include <iostream> using namespace std; const int Max = 5e6; long long dp[15][1 << 12]; int pre[Max], cur[Max]; int cnt, n, m; void solve(int l, int pre_, int cur_) { if (l > m) return; else if (l == m)//保存匹配好的状态 { pre[cnt] = pre_; cur[cnt++] = cur_; return; } solve(l + 2, (pre_ << 2) | 3, (cur_ << 2) | 3); //横着放置 //每次 pre_和cur_ 按位或3 是为了将(i,j)和(i,j+1)置1，表示横铺砖,铺完以后考虑(i,j+2) solve(l + 1, (pre_ << 1), (cur_ << 1) | 1); //竖着放置 //每次 cur_ 按位或1 是为了将(i,j)置1，表示竖铺砖,铺完以后考虑(i,j+1) solve(l + 1, (pre_ << 1) | 1, (cur_ << 1)); //不放置方块 } int main() { while (scanf("%d%d", &n, &m) == 2 && n && m) { cnt = 0; if (n < m) swap(n, m); solve(0, 0, 0);//使用深搜，找到所有“匹配”的状态 memset(dp, 0, sizeof(dp)); dp[0][(1 << m) - 1] = 1;//假想第0行是全1状态 for (int i = 1; i <= n; i++) { for (int j = 0; j < cnt; j++) dp[i][cur[j]] += dp[i - 1][pre[j]]; } printf("%lld\n", dp[n][(1 << m) - 1]); //cout << dp[n][(1 << m) - 1]<<"\n"; } return 0; } /* 1 2 1 3 1 4 2 2 2 3 2 4 2 11 4 11 0 0 */ /* ans 1 0 1 2 3 5 144 51205 */
