State compression DP

State compression dp Usually an integer represents a state , The so-called state varies in different problems .
Patients with a ：
291. Mondrian's dream
Portal
dp Stateful means , State calculation . State means , Represents a collection , It has its own attributes .
From this point of view .
Its status is expressed as dp[i][j], Its collective meaning is ： When the first i-1 After the column has been filled , From i-1 Column out to i The state of the column , And this state is expressed as j.(j How to understand it as a state , take j Convert to binary representation , Each represents a line , And when the first i When one is the first i-1 There is a wooden block protruding to the i That's ok .
Code not optimized , Optimized code .

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 12, M = 1 << N;
ll dp[N][M];
bool book[M];
int main() {
	int n, m;
	while (cin >> n >> m, n || m) {

		for (int i = 0; i < 1 << n; i++) {
			book[i] = 1;
			int cnt = 0;
			for (int j = 0; j < n; j++) {
				if (i >> j & 1) {
					if (cnt & 1)
						book[i] = 0;
					cnt = 0;
				} else cnt++;
			}
			if (cnt & 1)book[i] = 0;
		}
		memset(dp, 0, sizeof(dp));
		dp[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 && book[j | k]) {
						dp[i][j] += dp[i - 1][k];
					}
				}
			}
		}
		cout << dp[m][0] << endl;
	}
	return 0;
}

After deleting invalid combinations ：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; 
const int N = 12, M = 1 << N;
int n, m;
ll dp[N][M];
bool book[M];
vector<int>status[M];
int main() {
	
	while (cin >> n >> m, n || m) {
		for (int i = 0; i < 1 << n; i++) {
			bool is_valid = true;
			int cnt = 0;
			for (int j = 0; j < n; j++) {
				if (i >> j & 1) {
					if (cnt & 1) {
						is_valid = false;
						break;
					}
					cnt = 0;
				} else cnt++;
			}
			if (cnt & 1)is_valid = false;
			book[i] = is_valid;
		}
		for (int i = 0; i < 1 << n; i++) {
			status[i].clear();
			for (int j = 0; j < 1 << n; j++) {
				if ((i & j) == 0 && book[i | j]) {
					status[i].push_back(j);
				}
			}
		}
		memset(dp,0,sizeof (dp));
		dp[0][0]=1;
		for (int i = 1; i <= m; i++) {
			for (int j = 0; j < 1 << n; j++) {
				for (auto it : status[j]) {
					dp[i][j] += dp[i - 1][it];
				}
			}
		}
		cout << dp[m][0] << endl;
	}
	return 0;
}

Example 2 ： The shortest Hamilton route

#include<bits/stdc++.h>
using namespace std;
const int N = 21, M = 1 << N;
int dp[M][N];
int mp[N][N];

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &mp[i][j]);
		}
	}
	memset(dp,0x3f,sizeof (dp)); 
	dp[1][0] = 0;
	for (int i = 0; i < 1 << n; i++) {
		for (int j = 0; j < n; j++) {
			if (i >> j & 1) {
				for (int k = 0; k < n; k++) {
					if ((i - (1 << j)) >> k & 1) {
						dp[i][j] = min(dp[i][j], dp[i - (1 << j)][k] + mp[k][j]);
					}
				}
			}
		}
	}
	cout<<dp[(1<<n)-1][n-1];
	return 0;
}