题目介绍

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

求把 N×M 的棋盘分割成若干个 1×2 的长方形，有多少种方案。

方法一 朴素版状态压缩DP

1.算法细节

• 在动态规划前，如何确定一个可以保证数出所有摆放方法的途径？

类似于计数DP 整数划分，想要直接表示出一组方案非常抽象，整数划分的数法：dp[i][j]表示从数字 1 ~ i 选择，组成j数字的方案数量，类似完全背包问题，可以在容量允许的情况下取一个数字无限次，那么表示方法很简单
1 ~ i 挑选组成j的方案总数 = 挑选0个i的方案 + 挑选2个i的方案 + ···· + 挑选最大i的方案
本题可以从类似的特征提取划分集合的方式取考虑，当我们以合法的方式放横着的小方格后，（合法指当放置完毕时，竖着的小方格的放置不会出现卡格子的情况），其实剩下的格子竖着的小方格就唯一的被确定下来了。
那么总方案数其实就等于合法放置横着小方格的方案数啦

• 那么如何制定这个保证合法摆放的限制条件？

本题的状态表达式设置为f[i][j]：表示第i列中，从第i-1列放置横着小方格占用了第i列的状态j，第i列每行的状态都有可能是0或者是1，即为空或者被占。所以j可以作为一个位数为2 ^ N的二进制数字表示状态，其中N表示总行数，因此我们才可断定本题是一个状态压缩DP

摆放的限制很简单：首先我们得保证我们第i-1行放置左端点的横格和从第i-2行放置右端点的横格不会发生重叠冲突，保证横格都放在空位上。假设此时第i列的状态为j，表示第i-1列左端点的横格对第i列的占用情况，其实一个横格占了两列，这个j恰好也是当前i-1列左端点横格对第i-1列的占用情况 假设第i-2放置横格左端点的状态为k，那么这个k也代表了当前横格右端点对第i-1格的占用情况。那么此时若满足 j & k == 0，就代表着在第i-1列，不会产生前一列和后一列小方格撞车的情况啦。

光不撞车代表着交集不冲突，本题最难理解的st[j | k]是什么意思？

st[i]代表着i状态下，是否已经满足连续的0状态是否是偶数：这列空着的格子是不是能被竖格填满

当已经满足j & k == 0时，我们还要保证留下的空位刚好都能插入竖格，很简单，每列连续空着的格子得是偶数，此时刚好可以不重不漏的放入竖格，那么st[j | k]是什么意思？由上面的分析我们知道，j表示了i-1和i列被这列横格的占用，k表示了i-2和i-1列被这两列横格的占用，由人教版高一数学的集合部分我们知道，或的使用仅限两个完全不重合的集合，在我们已经判定j & k == 0时，也恰恰代表了这两列起点不同的横格属于不交集的集合，如果位运算取或，相相当于取并集，合并为一个大集合，如果此时状态为false，说明i-1列它没法插满竖格子

自此，本题全部难点细节均已分析完毕，还有一些小的细节部分，值得思考

为什么赋初值要给f[0][0] = 1？
首先，我们最开始枚举的i循环i列，一定是第二列，也就是从i=1开始，因为代表i-1列放横格，占用了i-1列和i列，显然第一个循环的案例就是f[1][0]—> j为0，然后k从0枚举到1 << n的情况，最后把f[1][0]的所有合法情况赋值完毕，那么f[1][0]最初借助的f[1][0] += f[0][0] - > 把合法的第一种情况给覆盖，相当于进入了起点，这也是为什么只需要给一个f[0][0]赋值就完成了初始化

j和k循环赋值能否颠倒？
其实我们可以把j和k颠倒理解，因为反正我们枚举的是满足条件if ((j & k) == 0 && st[j | k])的情况，赋值也是f[i][j] += f[i-1][k]，这种情况，我们只要保证合法的k和j满足条件，赋值是把i-1列的方案加到i列，那么最后赋值不管是f[i][j] += f[i-1][k]，还是f[i][k] += f[i-1][j]都无所谓
甚至本身i和j就会枚举到互为相反的数（不是相反数，是一个答案的逆序）
这里可以试试看把代码最后赋值的j和k调换，不会影响AC

2.具体代码

1 java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N = 12, n, m, M = 1 << N;
    static boolean[] st = new boolean[M];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        while (true) {
            String[] s1 = br.readLine().split(" ");
            n = Integer.parseInt(s1[0]);
            m = Integer.parseInt(s1[1]);
            if (n == 0 && m == 0) break;

            //st数组初始化
            for (int i = 0; i < 1 << n; i++) {
                //先处理为真
                st[i] = true;
                int cnt = 0;
                //状态是2的n次方 但移动位数还是n位
                for (int j = 0; j < n; j++) {
                    //该列出现了横着的格子
                    if ((i >> j & 1) == 1) {
                        if ((cnt & 1) == 1) {
                            st[i] = false;
                            break;
                        }
                    } else cnt++;
                }
                if ((cnt & 1) == 1) st[i] = false;
            }

            long[][] f = new long[N][M];
            f[0][0] = 1;
            for (int i = 1; i <= m; i++) {
                for (int j = 0; j <= 1 << n; j++) {
                    for (int k = 0; k <= 1 << n; k++) {
                        if ((j & k) == 0 && st[j | k]) {
                            f[i][j] += f[i-1][k];
                        }
                    }
                }
            }
            System.out.println(f[m][0]);
        }
    }
}

2 python3

N = 12
M = 1 << N

def dp(n, m):
    # 初始化st和f
    st = [1] * M
    f = [[0] * M for i in range(N)]

    # 把st数组进行合法赋值
    for i in range(1 << n):
        cnt = 0
        # 考察每一位是否出现1：即出现了横格
        for j in range(n):
            if (i >> j & 1):
                # 出现横格的情况下发现空格为奇数
                if cnt % 2:
                    st[i] = False
                    break
            else:   
                cnt += 1
        # 边界判断：最后一段距离一直没出现横格的情况
        if cnt % 2: st[i] = False

    # 动态规划
    f[0][0] = 1
    for i in range(1, m + 1):
        # 第 i-1 列起始点状态: 同时也代表伸到i列的状态
        for j in range(1 << n):
            # 第 i-2 列起始点状态：同时也代表伸到i-1列的状态
            for k in range(1 << n):
                if j & k == 0 and st[j | k]:
                    f[i][j] += f[i-1][k]

    return f[m][0]

if __name__ == '__main__':
    while 1:
        n, m = map(int, input().split())
        if not (n | m):    break
        print(dp(n, m))    

3 C++

#include <bits/stdc++.h>
using namespace std;

const int N = 12, M = 1 << N;//每行两种情况，故为2^N
long long f[N][M];//本题数据量大故用long long 不然会TLE
bool st[M];//当前列的状态的空格是否能被竖格填满

int main(){
    int n, m;
    //状态预处理判定
    while(cin >> n >> m, n || m)
    {
        //对这个n行出现的每列状态进行逐个判断
        for(int i=0; i < 1<<n; i++)
        {
            st[i] = true;//先处理为真
            int cnt = 0;//在一个空格区间连续0的个数
            //虽然状态是二进制处理，但是我们实际使用还是十进制数 
            for(int j=0; j<n; j++)
            {
                if(i >> j & 1)//枚举到了放格子的情况
                {
                    if(cnt & 1)//此时形成了一段空格子,检查此时格子奇偶性
                    {
                        st[i] = false;
                        break;//一旦为奇数即可结束，判断下一状态
                    }
                }
                else   cnt++;//为空，空格空间数量加一
            }
            //若此时一直到末尾还未出现实心格子
            if(cnt & 1) st[i] = false;
        }

        memset(f, 0, sizeof f);//初始化状态表达式
        f[0][0] = 1;//初始化初值：此时第0列没有横格，也就相当于全部为竖格，故为1种方案

        for(int i=1; i<=m; i++)//枚举每一列
            for(int j=0; j < 1<<n; j++)//枚举第i-1列起始点每种状态
                for(int k=0; k < 1<<n; k++)//枚举第i-2列起始点的每种状态
                    if((j & k) == 0 && st[j | k])
                        f[i][j] += f[i-1][k];
        //由定义出发，当前m-1列的方案均已结束赋值，来到下一层循环
        //进入到第m列，此时没有伸出边界的横格，即最后状态
        cout << f[m][0] << endl;
    }
    return 0;
}