状压DP
状压 DP 是动态规划的一种，通过将状态压缩为整数来达到优化转移的目的。
例题
https://www.luogu.com.cn/problem/P1896
思路
一行中所有放置的状态可以用二进制数表示：如01000111（1代表当前位置放置物品）
因此，我们可以先找出所有的合法状态，(利用dfs进行递归)
并用sit[i]记录第i个状态的表示的十进制数，sta[i]记录第i个状态所放置物品数量
然后枚举每一行的状态，并对上一行的状态继承转移（前提是互相合法）
转移方程
Code
点击查看代码
const int maxn = 1e5 + 10;
int n, m;
int sit[maxn], sta[maxn], cnt;
// 当前的状态//当前状态所用的数量//状态总数
int dp[15][2010][110]; // ijk;记录前i行，第i行状态j，总用k个的方案
void dfs(int x, int num, int cur) {
if (cur >= n) {
sit[++cnt] = x;
sta[cnt] = num;
return;
}
dfs(x, num, cur + 1);
dfs(x + (1 << cur), num + 1, cur + 2);
}
bool check(int x, int y) { // 利用位运算的性质判断之间是否合法
if (sit[x] & sit[y]) return false;
if ((sit[x] << 1) & sit[y]) return false;
if (sit[x] & (sit[y] << 1)) return false;
return true;
}
void solve() {
cin >> n >> m;
dfs(0, 0, 0); // 预处理出一行中所有合法状态
// 用cnt记录合法状态数量
for (int i = 1; i <= cnt; i++) // 对第一行的状态方案赋值
dp[1][i][sta[i]] = 1;
for (int i = 2; i <= n; i++) { // 枚举行
for (int j = 1; j <= cnt; j++) { // 枚举当前行状态
for (int k = 1; k <= cnt; k++) { // 枚举上一行状态
if (!check(j, k)) continue; // 不合法
for (int l = sta[j]; l <= m; l++) { // 枚举全部合适的数量
dp[i][j][l] += dp[i - 1][k][l - sta[j]]; // 方案累加
}
}
}
}
int ans = 0;
for (int i = 1; i <= cnt; i++) // 方案累加
ans += dp[n][i][m];
cout << ans;
}