题目链接：https://www.acwing.com/problem/content/description/293/
题目描述
求把 N×M 的棋盘分割成若干个 1×2 的的长方形，有多少种方案。
例如当 N=2，M=4 时，共有 5 种方案。当 N=2，M=3 时，共有 3 种方案。输入描述
输入包含多组测试用例。
每组测试用例占一行，包含两个整数 N 和 M。
当输入用例 N=0，M=0 时，表示输入终止，且该用例无需处理。输出描述
每个测试用例输出一个结果，每个结果占一行。
1≤N,M≤11示例
输入
1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0输出
1
0
1
2
3
5
144
51205分析
约定
棋盘的行数和列数分别为n，m
切入点
将棋盘按照1*2的矩阵划分，则矩阵仅有两种放法，横着放和竖着放。当确定了那些格子横着放矩阵，那剩下的格子必定由竖着放的矩阵填满，因此，横着放的矩阵的分割方案数即等于总的分割方案数。我们只需要考虑合法的横着放矩阵的方案数即可。
合法，是指剩余的空间能够被竖着的矩阵填满，即横着的方案确定后，纵向连续的空格数必须为偶数，否则不能填满整个棋盘。状态表示
f(i,j)表示满足如下条件分割方案的数量：
- 前i-1列横着放矩阵的方案已确定
- 第i-1列伸出来的格子在第i列的状态为j
此处的j与其它的DP问题不同，它代表的是一种状态，应将其看作是一个二进制数，每一位代表一列中某一个格子的状态，0为空，1为被我们分割的矩阵包含。二进制数的大小范围为 0 ~ 1<<n，左闭右开。
状态划分与计算
对于f(i,j)，我们还是按照以往的思路，试着将达成f(i,j)的最后一步操作进行划分，也就是在f(i-1,k)的情况下操作第i-1列，使之变成f(i,j)。显然，f(i,j)=sum(f(i-1,k))，要求f(i-1,k)必须能转移到f(i,j)。
转移的条件如下：
- k&j=0，表示横向矩阵放的不冲突
- k|j 连续0的个数为偶数 ，表示第i-1列这个已确定的列能被纵向的矩阵填充。
需要注意，第i-1列的填充情况是在k，j都确定时才确定的，只有此时讨论合法才有意义。
为了减少时间复杂度，我们引入布尔数组st，对于一列已经确定的状态i，st[i]为true表示其合法，否则非法。还引入了vector
边界处理
f(1,0)=1，其余都是0。这是从实际意义上出发，也可以从满足f(2,j)的实际要求出发。
AC代码
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int N = 13, M = 1 << 12;
long long f[N][M]; //存在一些大数据 记得用long long
bool st[M];
vector<int> state[M];
int n, m;
int main()
{
while (cin >> n >> m, n || m) //逗号表达式 相当优雅
{
for (int i = 0; i < 1 << n; i++)
{
int cnt = 0;
st[i] = true;
for (int j = 0; j < n; j++)
{
if (i >> j & 1)
{
if (cnt & 1)
{
st[i] = false;
break;
}
cnt = 0;
}
else
cnt++;
}
if (cnt & 1) //此处考虑该列状态可能不是1结尾 所以得结尾处再判断一次
st[i] = false;
}
for (int i = 0; i < 1 << n; i++)
{
state[i].clear();
for (int j = 0; j < 1 << n; j++) //j表示i的前一列
{
if ((i & j) == 0 && st[i | j])
state[i].push_back(j);
}
}
memset(f, 0, sizeof(f));
f[1][0] = 1;
for (int i = 2; i <= m+1; i++)
{
for (int j = 0; j < 1 << n; j++)
{
for (auto k : state[j])
f[i][j] += f[i - 1][k];
}
}
cout << f[m+1][0] << endl; //前m列确定且没伸到m+1列 正好是结果
}
return 0;
}
