鉴于多次遇到铺砖问题，因此目前遇到对此类问题进行总结：

铺砖问题主要分类：

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
*/