状态压缩 DP，或状压 DP，是对状态的一种优化。相比于普通 DP，通过将高维状态压缩成一个数，减少了维度，并使维度更易于存储与维护。同时这样与 bitset 一样利用了计算机在 \(O(1)\) 内处理位运算的能力，大幅度优化了时间复杂度。
一般当题目中的状态由多个 \(0\) / \(1\) 组成，数量不一定，且需要对状态进行操作时，可以使用状压 DP 优化状态。
实现
状压 DP 的核心在于状态压缩。前者是一种算法，而后者是一种思想，且前者基于后者。
状态压缩的思想：将一个由 \(0\) / \(1\) 构成的状态压缩为一个二进制数并用其表示。这样便于存储、传递、枚举与维护，并充分利用计算机 \(O(1)\) 处理位运算的能力。在 DP 问题中，并不是所有状态都是有效的，因此为了节省空间，减小常数，应尽量减少无效的状态，而状态压缩的思想恰好满足这个要求，因为它无效的状态都可以被去除掉，这就是它被广泛应用于 DP，并形成状压 DP 的根本原因。
例题：Luogu P1896 [SCOI2005] 互不侵犯
考虑怎么设状态。发现假设当前枚举到第 \(i\) 行第 \(j\) 列，当前状态与它左边的方格和上面的方格都有关系，也就是说一个状态要牵扯到它本身行与它的上一行，极难维护，于是考虑进行压缩。
发现 \(N\) 的范围很小，我们其实不用一个一个方格枚举，而可以一行一行枚举，只要当前行与上一行整体没有冲突，就可以累计答案了。这样每行都只与上一行有关联，只需要在状态中维护当前行的状态就可以了。
每一行有 \(N\) 个方格，也就是说状态一共有 \(N\) 维，这样就不方便维护了。
因为每维都是 \(0\) / \(1\)，所以我们可以把一行的状态压缩为一个数，这就是状态压缩。这样，我们就可以仅用两维表示出所有状态：\(i\) 表示当前行标，\(j\) 表示当前行的状态。
现在考虑如何进行转移。状态 \((i - 1, j)\) 能转移到 \((i, k)\) 当且仅当 \(j\)，\(k\) 合法且 \(j\) 可以放在 \(k\) 的上面。
一个状态合法，代表其中不存在两个相邻位为 \(1\)。两个状态能叠，代表不存在同位上两个状态都为 \(1\)。我们需要对这两种情况进行判断。对于这道题来说，暴力枚举每一位已经可以 AC 了。
但其实对状态进行压缩之后，自然地产生了一种新的对于状态的处理方式：位运算。
我们可以把过程叙述转化为公式。
一个状态合法，当且仅当它满足公式 i & (i << 1) == 0。两个状态能叠，当且仅当 i & j == 0。
这样状态处理一般会快得多。
这样就做完了。
上代码！
#include<bits/stdc++.h>
using namespace std;
unsigned long long N, K, dp[10][100][512];
unsigned long long bitcount(unsigned long long c){
if (c == 0) return 0;
else return (c&1)+bitcount(c>>1);
}
int main(){
cin >> N >> K;
dp[0][0][0] = 1;
for (int i = 1;i <= N;i++)
for (int j = 0;j <= K;j++){
for (int k = 0;k < (1<<N);k++){
if ( (k & (k<<1)) > 0 || bitcount(k) > j) continue;
for (int k0 = 0;k0 < (1<<N);k0++){
if ((k0 & (k0<<1)) > 0 || (k&k0) > 0 || ((k<<1)&k0) > 0 || ((k>>1)&k0) > 0) continue;
dp[i][j][k] += dp[i-1][j-bitcount(k)][k0];
}
}
}
unsigned long long sum = 0;
for (int i = 0;i < (1<<N);i++) sum += dp[N][K][i];
cout << sum;
}
这道题就体现了状压 DP 的两个作用：优化状态，优化处理。
常见应用
覆盖问题
这是最简单的一类应用，求在矩阵上以某种方式覆盖的方案数量。
我们可以使用状态压缩维护最近几行的状态，然后按题意转移即可。
相对于普通 DP，这样做的优点是可以一行一行处理，状态较为简洁，而且可以通过位运算实现对行的各种操作。
常见操作：
| 操作 | 表达式 |
|---|---|
| 检测两行重叠元素 | \(x\and y\) |
| 检测两行不同元素 | \(x\or y\) |
| 将行向左/右平移 | \(x << k\) / \(x >> k\) |
例题：Luogu P1879 [USACO06NOV] Corn Fields G
先按照这种题的套路（？）设出状态：\(f_{i, j}\) 表示第 \(i\) 行状态为 \(j\) 的方案数。
首先每一行必须合法，一个条件是该行本身不能有相邻元素。即将这一行位移后应不与原行有共同点。于是第一个条件：j & (j << 1) == 0。
同时该行也不能再贫瘠的草地上种东西，即它与贫瘠草地在本行的出现不得出现共同点。我们将贫瘠草地的状态预处理并设为 \(b[i]\)，则 b[i] & i == 0。
然后这行与上一行也要组成合法状态。我们需要枚举上一行的状态，同理得 j & k == 0。
这就是所有的条件。
上代码！
#include<bits/stdc++.h>
#define MAXSTATE 4096
using namespace std;
int n, m, state[105], f[105][MAXSTATE+5];
int main(){
cin >> m >> n;
for (int i = 1;i <= m;i++){
int cur = 0, tmp;
for (int j = 1;j <= n;j++){
cin >> tmp;
cur <<= 1;
cur |= tmp;
}
state[i] = cur;
}
f[0][0] = 1;
for (int i = 1;i <= m;i++){
for (int j = 0;j <= pow(2, n)-1;j++){
if ((j|state[i]) > state[i]) continue;
if ((j&(j<<1)) > 0 || (j&(j>>1)) > 0) continue;
for (int k = 0;k <= pow(2, n)-1;k++){
if ((k|state[i-1]) > state[i-1]) continue;
if ((k&(k<<1)) > 0 || (k&(k>>1)) > 0 || (j&k) > 0) continue;
f[i][j] += f[i-1][k];
}
}
}
int s = 0;
for (int i = 0;i <= pow(2, n)-1;i++){
s += f[m][i];
s %= 100000000;
}
cout << s % 100000000;
}
可见这种类型的题极其套路化，关键在于如何将覆盖信息转化为位运算。
图上不相交路径问题
有时我们要统计图上不相交的路径条数，这时当点数较少时我们可以使用状压 DP，使用状态记录那些点被访问过，再进行 DP。这种问题尤其要注意时空限制，毕竟在指数级别复杂度时很小的数据也能导致超时。
例题：CF11D. A Simple Task
非常值得做的一道题，这个模板会在很多地方遇到
这道题有很多很好想的错误做法，这里只讲正确的做法。
求每个点只经过一次的环，数据范围 \(n\le 19\)，自然想到状压 DP。稍作思考后发现当前状态与访问过的点和当前的点有关，于是设出状态 \(f_{i, j}\) 代表访问过的点的状态为 \(i\)，现在在 \(j\) 的路径条数。
然后考虑去重。我们发现每个环被访问次数相当于环上点的个数，于是我们使用代表元法，为每个环指派一个代表元。因为我们是在点上 DP，直接选择其最小节点作为代表元即可。
这里又体现了状压 DP 的优势。其最小的节点相当于其状态的最低位，在 \(O(1)\) 时间即可算出，为 log2(i&-i)。
然后最后再去掉长度为 \(2\)，即 \(a\rarr b\rarr a\) 类的环即可。这样的环一共有 \(m\) 个。
上代码！
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 19, MAXM = 405;
struct edge {
int u, v;
}e[2 * MAXM];
int n, m, f[1 << MAXN][MAXN + 1], lg2[1 << MAXN];
vector<int> states[MAXN];
int pop (int x) {
return x ? (x & 1) + pop (x >> 1) : 0;
}
int cor (int x) {
return 1 << (x - 1);
}
signed main () {
cin >> n >> m;
for (int i = 1;i < (1 << n);i++) lg2[i] = lg2[i / 2] + 1;
for (int i = 1;i <= m;i++) {
cin >> e[2 * i - 1].u >> e[2 * i - 1].v;
e[2 * i].v = e[2 * i - 1].u;
e[2 * i].u = e[2 * i - 1].v;
}
for (int i = 0;i < (1 << n);i++) {
states[pop(i)].push_back(i);
}
int ans = 0;
for (int i = 1;i <= n;i++) f[cor(i)][i] = 1;
for (int len = 1;len <= n;len++){
for (int i: states[len]) {
for (int j = 1;j <= 2 * m;j++) {
if (!(i & cor (e[j].u))) continue;
if (e[j].v < lg2[i&-i]) continue;
if (i & cor(e[j].v)) {
if (e[j].v == lg2[i&-i]) ans += f[i][e[j].u];
continue;
}
f[i | cor (e[j].v)][e[j].v] += f[i][e[j].u];
}
}
}
cout << (ans - m) / 2 << endl;
return 0;
}
以上只是状压 DP 最经典的几种应用，实际上其他的应用还要比这多得多，重在理解状态压缩的思想。
注意事项
- 状态压缩的题目特点是数据范围比较小，且关心一些元素的存在状态。解决时需要特别注意数据范围。一个指数级别的算法很容易被卡掉。
- 要尽量利用位运算的优势，减少常数。（通常是因为这类的题需要卡掉很多暴力做法，所以时空范围较为严格）
- 要充分理解状态压缩的思想。有可能这种思想会运用于非 DP 的题，这时它依然有以上作用。
- 在进行位运算是要分清楚位标和位值的区别，使用正确的值进行运算。