一：蒙德里安的梦想
求把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
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 const int N = 12; 6 7 bool st[1 << N]; 8 long long dp[N][1<<N]; 9 int n, m; 10 11 int main(){ 12 while(cin >> n >> m , n||m){ 13 //预处理所有可能的状态是否有奇数个空格 14 for(int i = 0;i < 1 << n;++i){ 15 int cnt = 0; 16 st[i] = true; 17 for(int j = 0;j < n;++j) 18 if(i >> j & 1){ 19 if(cnt % 2) st[i] = false;//代表当前状态有奇数个空格 20 cnt = 0; 21 }else ++cnt; 22 23 if(cnt % 2) st[i] = false; 24 } 25 //dp 26 memset(dp, 0, sizeof dp); 27 dp[0][0] = 1; 28 for(int i = 1;i <= m;++i) 29 for(int j = 0;j < 1 << n;++j)//j 和 k谁先枚举都可以 30 for(int k = 0;k < 1 << n;++k) 31 if(!(j & k) && st[j | k]) 32 dp[i][k] += dp[i-1][j];//从i-1到i的方案数 += 从i-2到i-1的方案数 33 34 cout << dp[m][0] << endl; 35 } 36 return 0; 37 }
二：最短Hamilton路径
给定一张 nn 个点的带权无向图，点从 0~n-1 标号，求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。
第一行输入整数nn。
接下来nn行每行nn个整数，其中第ii行第jj个整数表示点ii到jj的距离（记为a[i,j]）。
对于任意的x,y,zx,y,z，数据保证 a[x,x]=0，a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]>=a[x,z]。
输出一个整数，表示最短Hamilton路径的长度。
1≤n≤201≤n≤20
0≤a[i,j]≤1070≤a[i,j]≤107
5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0
18
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int N = 21; 5 6 int dp[1 << N][N]; 7 int w[N][N]; 8 9 int main(){ 10 int n;cin >> n; 11 for(int i = 0;i < n;++i) 12 for(int j = 0;j < n;++j) 13 cin >> w[i][j]; 14 memset(dp, 0x3f, sizeof dp); 15 dp[1][0] = 0;//代表经过了编号0那个点目前在0那个点的最小距离是0 16 for(int i = 1;i < (1 << n);++i) 17 for(int j = 0;j < n;++j) 18 if((i >> j) & 1) 19 for(int k = 0;k < n;++k) 20 if(i >> k & 1) 21 dp[i][j] = min(dp[i][j], dp[i-(1<<j)][k] + w[k][j]);// 0到k更新0到j 22 cout << dp[(1<<n)-1][n-1] << endl; 23 return 0; 24 }
原文：https://www.cnblogs.com/sxq-study/p/12335986.html