动态规划系统课程 · 第七讲：状态压缩 DP¶
这一讲进入动态规划中非常重要的一类：
状态压缩 DP（Bitmask DP）¶
前面我们学习 DP 时，状态通常比较简单：
dp[i]
dp[i][j]
dp[l][r]
dp[u][0]
但有一类问题会遇到一个困难：
状态不仅需要记录“当前在哪里”，还需要记录“哪些东西已经使用过”。
例如：
已经访问：
1、3、5
当前在：
3
如果直接记录集合：
{1,3,5}
程序处理起来很麻烦。
状态压缩 DP 的核心思想就是：
使用二进制的每一位表示一个元素是否被选择。
一、什么是状态压缩？¶
假设有 5 个城市：
1 2 3 4 5
我们使用一个二进制数表示访问状态。
规定：
第 0 位 → 城市 1
第 1 位 → 城市 2
第 2 位 → 城市 3
第 3 位 → 城市 4
第 4 位 → 城市 5
例如：
00101
表示：
城市 1：访问
城市 2：没有访问
城市 3：访问
城市 4：没有访问
城市 5：没有访问
也就是：
{1, 3}
二、为什么二进制特别适合表示集合？¶
因为二进制每一位只有：
0
1
正好可以表示：
0 → 没有选择
1 → 已经选择
所以：
集合
可以变成：
二进制整数
例如：
集合 {1,3,4}
对应：
1101
三、状态压缩最重要的三个操作¶
假设：
int mask;
1. 判断第 i 个元素是否选择¶
使用：
mask & (1 << i)
例如：
if (mask & (1 << i)) {
// i 已经选择
}
2. 把 i 加入集合¶
使用：
mask | (1 << i)
例如：
int newMask = mask | (1 << i);
3. 从集合中删除 i¶
使用：
mask ^ (1 << i)
前提是：
i原来一定在集合中。
更通用的写法：
mask & ~(1 << i)
四、最重要的操作：枚举集合中的元素¶
如果：
mask
表示已经选择的集合，那么我们经常需要：
枚举所有已经选择的元素。
最简单的写法：
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) {
// i 在集合中
}
}
五、一个非常重要的概念：状态数量¶
如果有 n 个元素。
每个元素有两种状态：
选择
不选择
所以一共有：
$$
2^n
$$
种状态。
例如：
| n | 状态数 |
|---|---|
| 5 | 32 |
| 10 | 1024 |
| 15 | 32768 |
| 20 | 1048576 |
| 25 | 33554432 |
因此状态压缩 DP 通常适用于：
$$
n\le 20
$$
左右的问题。
具体上限取决于转移复杂度和内存。
六、第一道经典题：TSP¶
我们开始状态压缩 DP 最经典的问题：
旅行商问题¶
有 n 个城市。
城市之间有距离：
dist[i][j]
要求：
从城市
0出发，每个城市恰好访问一次，最后回到城市0，求最短路线长度。
例如：
2
↗ ↘
0 3
↖ ↙
1
七、为什么普通 DP 不够？¶
如果只写：
dp[i]
表示：
当前在城市
i。
这是不够的。
因为：
当前都在城市 3
可能存在两种情况：
0 → 1 → 2 → 3
或者：
0 → 2 → 1 → 3
虽然当前都是：
3
但已经访问的城市集合不同。
所以状态必须同时记录：
- 已访问哪些城市
- 当前在哪里
于是：
$$
\boxed{dp[S][i]}
$$
八、TSP 状态定义¶
定义：
$$
dp[S][i]
$$
表示：
已经访问的城市集合为
S，当前位于城市i时的最短路径长度。
其中：
S
是一个二进制集合。
九、初始化¶
从城市 0 出发。
一开始只访问了城市 0：
00001
所以：
$$
dp[1][0]=0
$$
如果从 0 开始编号：
dp[1 << 0][0] = 0;
十、状态转移¶
假设：
dp[S][i]
表示：
已经访问集合
S，现在在i。
下一步去：
j
要求：
j还没有访问。
判断：
if (!(S & (1 << j)))
然后：
S
↓
S ∪ {j}
新的集合：
newS = S | (1 << j);
路径增加：
$$
dist[i][j]
$$
所以：
$$
dp[S\cup{j}][j]
=
\min
\left(
dp[S\cup{j}][j],
dp[S][i]+dist[i][j]
\right)
$$
十一、最终答案¶
当所有城市都访问完成：
S = (1 << n) - 1
例如 n=4：
1111
表示：
所有城市都访问了
此时我们在某个城市 i。
但题目要求：
最后回到城市 0。
因此：
$$
answer
=
\min_i
\left(
dp[all][i]+dist[i][0]
\right)
$$
注意：
不要忘记最后回到起点。
十二、完整 C++ 实现¶
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<vector<long long>> dist(
n,
vector<long long>(n)
);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> dist[i][j];
}
}
const long long INF = 4e18;
int total = 1 << n;
vector<vector<long long>> dp(
total,
vector<long long>(n, INF)
);
// 从城市 0 出发
dp[1][0] = 0;
for (int mask = 0; mask < total; mask++) {
for (int i = 0; i < n; i++) {
if (dp[mask][i] == INF)
continue;
// 尝试去城市 j
for (int j = 0; j < n; j++) {
// j 已经访问
if (mask & (1 << j))
continue;
int newMask =
mask | (1 << j);
dp[newMask][j] =
min(
dp[newMask][j],
dp[mask][i]
+ dist[i][j]
);
}
}
}
int all = (1 << n) - 1;
long long answer = INF;
// 最后回到 0
for (int i = 0; i < n; i++) {
answer = min(
answer,
dp[all][i] + dist[i][0]
);
}
cout << answer << '\n';
return 0;
}
十三、一定要理解 mask¶
这是状态压缩 DP 最重要的基础。
假设：
n = 4
那么：
mask
可能是：
0000
0001
0010
0011
0100
...
1111
其中：
1111
表示：
4 个城市全部访问。
而：
0101
表示：
第 0 个和第 2 个城市已经访问。
十四、位运算详细解释¶
假设：
int mask = 5;
二进制：
0101
判断城市 0¶
mask & (1 << 0)
也就是：
0101
&
0001
----
0001
结果非零。
所以：
城市 0 已访问。
判断城市 1¶
mask & (1 << 1)
即：
0101
&
0010
----
0000
结果为 0。
所以：
城市 1 没有访问。
十五、加入一个城市¶
假设：
mask = 0101
现在访问城市 1。
城市 1 对应：
0010
使用：
mask | (1 << 1)
得到：
0101
|
0010
----
0111
于是：
0101
变成：
0111
十六、第二道经典题：集合覆盖 DP¶
现在把 TSP 稍微抽象一下。
假设有：
n 个任务
每个任务可能被某种操作覆盖。
我们希望：
用最少的操作覆盖所有任务。
如果 mask 表示：
当前已经覆盖的任务集合。
那么可以定义：
$$
dp[mask]
$$
表示：
覆盖集合
mask所需要的最小代价。
这就是最基础的：
集合 DP¶
十七、一个简单模型¶
假设有 4 个任务：
1 2 3 4
有三个操作：
操作 A：覆盖 1、2
操作 B：覆盖 2、3
操作 C：覆盖 3、4
每个操作有一个费用。
例如：
A：5
B：2
C：4
目标：
覆盖全部任务，最小费用。
十八、状态定义¶
$$
dp[mask]
$$
表示：
当前已经覆盖
mask中的任务所需要的最小费用。
初始：
$$
dp[0]=0
$$
因为：
什么任务都没有覆盖时，费用是 0。
十九、状态转移¶
假设当前：
mask
选择一个操作，它覆盖：
cover
新的覆盖集合：
$$
newMask=mask\ |\ cover
$$
那么：
$$
dp[newMask]
=
\min(
dp[newMask],
dp[mask]+cost
)
$$
二十、完整 C++ 代码¶
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> cover(m);
vector<long long> cost(m);
for (int i = 0; i < m; i++) {
int k;
cin >> k;
int mask = 0;
for (int j = 0; j < k; j++) {
int x;
cin >> x;
// 任务编号从 1 开始
--x;
mask |= (1 << x);
}
cover[i] = mask;
cin >> cost[i];
}
const long long INF = 4e18;
int total = 1 << n;
vector<long long> dp(
total,
INF
);
dp[0] = 0;
for (int mask = 0; mask < total; mask++) {
if (dp[mask] == INF)
continue;
for (int i = 0; i < m; i++) {
int newMask =
mask | cover[i];
dp[newMask] =
min(
dp[newMask],
dp[mask] + cost[i]
);
}
}
int all = (1 << n) - 1;
if (dp[all] == INF)
cout << -1 << '\n';
else
cout << dp[all] << '\n';
return 0;
}
二十一、这道题和 TSP 有什么关系？¶
TSP：
dp[mask][i]
集合覆盖：
dp[mask]
共同点：
都使用
mask描述“已经完成了什么”。
区别：
TSP 还需要知道：
当前位置 i
所以：
$$
dp[mask][i]
$$
而集合覆盖只关心：
已经覆盖哪些任务
所以：
$$
dp[mask]
$$
二十二、第三道经典题：状压 DP 的“选数”问题¶
现在看一个更加基础的模型。
给定 n 个数：
a1, a2, ..., an
要求选择若干个数。
如果选择状态由：
mask
表示，那么：
mask
就是一个集合。
例如：
mask = 10110
表示选择：
2、3、5
二十三、为什么不直接使用普通 DFS？¶
当然可以。
例如：
void dfs(int pos) {
// 不选
dfs(pos + 1);
// 选
dfs(pos + 1);
}
这实际上是在枚举所有子集。
但是：
DFS 只能告诉你当前走到了哪里。
如果不同的路径最终产生相同的状态，就会重复计算。
DP 的作用就是：
把相同状态合并。
这就是状态压缩 DP 的价值。
二十四、一个非常重要的思想：状态合并¶
假设有：
1 → 2
1 → 3
最终可能产生同一个状态：
mask = 10101
如果这个状态之后的计算完全相同：
那么前面的过程就没有必要重复计算。
只需要保存：
dp[10101]
即可。
这就是 DP 的核心思想之一：
相同状态只计算一次。¶
二十五、状态压缩 DP 的复杂度¶
最常见：
$$
2^n
$$
个状态。
如果每个状态枚举 n 个选择：
$$
O(n2^n)
$$
如果再加一层：
$$
O(n^2 2^n)
$$
因此：
n = 20
时：
$$
2^{20}=1,048,576
$$
大约一百万个状态。
这是可以接受的。
但：
n = 30
时：
$$
2^{30}\approx10.7亿
$$
通常就非常困难了。
二十六、状态压缩 DP 的常见状态形式¶
以后会经常看到：
形式一¶
$$
dp[mask]
$$
表示：
集合
mask的最优答案。
形式二¶
$$
dp[mask][i]
$$
表示：
已经完成
mask，当前位于i。
TSP 就属于这一类。
形式三¶
$$
dp[mask][i][j]
$$
表示：
集合
mask+ 两个额外状态。
这种情况状态更多，需要特别注意复杂度。
二十七、状态压缩 DP 最重要的思维¶
以后看到：
n很小，通常n ≤ 20
并且题目出现：
- 每个元素选/不选
- 已经使用了哪些元素
- 已经访问哪些城市
- 已经完成哪些任务
- 集合
- 子集
- 每个元素只能使用一次
马上想到：
二进制状态压缩¶
二十八、四种常用位运算¶
建议学生直接背下来，但更重要的是理解。
假设第 i 位表示元素 i。
判断¶
mask & (1 << i)
加入¶
mask | (1 << i)
删除¶
mask & ~(1 << i)
翻转¶
mask ^ (1 << i)
二十九、如何枚举所有子集？¶
如果有 n 个元素：
for (int mask = 0; mask < (1 << n); mask++) {
// mask 就是一个子集
}
这是最基础的子集枚举。
三十、如何枚举 mask 的所有子集？¶
这是状态压缩 DP 中非常重要的技巧。
例如：
mask = 10110
我们想枚举：
10110
10100
10010
10000
00110
00100
00010
00000
可以使用：
for (int sub = mask; sub; sub = (sub - 1) & mask) {
// sub 是 mask 的一个非空子集
}
这个技巧非常重要。
三十一、为什么 (sub - 1) & mask 可以枚举子集？¶
例如：
mask = 10110
假设：
sub = 10100
减一：
10011
再：
10011
&
10110
-----
10010
得到：
10010
仍然是 mask 的子集。
不断重复：
sub = (sub - 1) & mask
最终就会遍历所有子集。
复杂度：
$$
O(3^n)
$$
这会在后面的高级状态压缩 DP 中非常重要。
三十二、状态压缩 DP 与普通 DP 的区别¶
普通 DP：
状态数量通常是 n
n²
n³
状态压缩 DP：
状态数量通常是 2^n
所以它的核心交换关系是：
用指数级状态数量，换取对“小规模集合问题”的高效精确求解。
三十三、目前的 DP 知识地图¶
到这里已经进入一个比较完整的体系：
动态规划
│
├── ① 线性 DP
│ ├── LIS
│ ├── LCS
│ └── 编辑距离
│
├── ② 背包 DP
│ ├── 01 背包
│ ├── 完全背包
│ ├── 多重背包
│ └── 分组背包
│
├── ③ 区间 DP
│ ├── 石子合并
│ ├── 回文
│ └── 矩阵链
│
├── ④ 树形 DP
│ ├── 最大独立集
│ ├── 没有上司的舞会
│ └── 树上最大路径
│
├── ⑤ DAG DP
│ ├── 最长路
│ ├── 最短路
│ └── 路径计数
│
└── ⑥ 状态压缩 DP
├── 子集 DP
├── TSP
├── 集合覆盖
└── 位运算
三十四、本讲最重要的三个公式¶
判断元素是否在集合中¶
$$
\boxed{
mask\ \&\ (1<<i)
}
$$
加入元素¶
$$
\boxed{
mask|(1<<i)
}
$$
状压 DP 最经典状态¶
$$
\boxed{
dp[mask][i]
}
$$
它表示：
完成集合
mask，当前处于状态i时的最优答案。
三十五、一个非常重要的判断口诀¶
以后做竞赛题时看到：
n 很小
+
每个元素有选/不选
+
还要记录已经选择了哪些
马上想到：
二进制 → 集合 → 状态压缩 DP
如果进一步出现：
当前在哪里
那么马上想到：
dp[mask][i]
如果题目出现：
每个城市访问一次
马上想到：
TSP / 状态压缩 DP
三十六、下一讲：数位 DP¶
下一讲我们继续进入一个非常有特色的 DP：
第八讲：数位 DP¶
数位 DP 专门解决这类问题：
统计
[L,R]范围内满足某种数字条件的整数个数。
例如：
1 ~ 10^18中有多少个数字不包含4？1 ~ 10^18中有多少个数字相邻两位不同？1 ~ N中有多少个数字的数位和等于S？L ~ R中有多少个数字满足某种数位限制？
届时会重点学习：
$$
\boxed{dp[pos][state][limit][lead]}
$$
这几个状态参数分别是什么意思，以及为什么数位 DP 经常使用：
答案(1 ~ R)
-
答案(1 ~ L-1)
来解决 [L,R] 的问题。
到那时，我们会把动态规划进一步推进到：
线性 DP → 背包 → 区间 → 树形 → DAG → 状态压缩 → 数位 DP → 计数 DP → 概率 DP → DP 优化
这套体系基本就覆盖了中学信息学竞赛中最重要的动态规划框架。