描述
求把N*M的棋盘分割成若干个1*2的的长方形，有多少种方案。
例如当N=2，M=4时，共有5种方案。当N=2，M=3时，共有3种方案。
如下图所示：
输入格式
输入包含多组测试用例。
每组测试用例占一行，包含两个整数N和M。
当输入用例N=0，M=0时，表示输入终止，且该用例无需处理。
输出格式
每个测试用例输出一个结果，每个结果占一行。
数据范围
1≤N,M≤111≤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题源POJ 2411
参考博客 https://blog.csdn.net/u013480600/article/details/19569291
#include <iostream> #include <cstdio> //EOF,NULL #include <cstring> //memset #include <cmath> //ceil,floor,exp,log(e),log10(10),hypot(sqrt(x^2+y^2)),cbrt(sqrt(x^2+y^2+z^2)) #include <algorithm> //fill,reverse,next_permutation,__gcd, #include <string> #include <vector> #include <queue> #include <stack> #include <map> using namespace std; #define rep(i, a, n) for (int i = a; i < n; ++i) #define sca(x) scanf("%d", &x) #define sca2(x, y) scanf("%d%d", &x, &y) #define sca3(x, y, z) scanf("%d%d%d", &x, &y, &z) #define pri(x) printf("%d ", x) #define pb push_back #define mp make_pair typedef pair<int, int> P; typedef long long ll; const ll inf = 99999999999; const int INF = 0x3f3f3f3f; const int mod = 1e9+7; const int maxn = 105; const int N = 1e4 + 5; int t, n, m; int cnt, ans, ed; ll dp[15][1<<15]; int path[50000][2]; int h, w; void dfs(int l, int now, int pre) { if (l > w) { return; } if (l == w) { path[cnt][0] = pre; path[cnt++][1] = now; return; } dfs(l + 2, (now << 2)|3, (pre << 2)|3); // 竖放，当前行为1，上一行为0 dfs(l + 1, (now << 1)|1, (pre << 1)); // 横放 当前行和上一行都为11 dfs(l + 1, (now << 1), (pre << 1)|1); //不放，上一行为1，当前行为0 } int main() { while (sca2(h, w) && h && w) { if (h < w) { swap(h, w); } cnt = 0; dfs(0, 0, 0); memset(dp, 0, sizeof dp); ed = (1 << w) - 1; dp[0][ed] = 1; for (int i = 0; i < h; i++) { for (int j = 0; j < cnt; j++) { dp[i + 1][path[j][1]] += dp[i][path[j][0]]; } } printf("%lld ", dp[h][ed]); } return (0); }