状态压缩动态规划 (Bitmask DP)¶
状态压缩动态规划（简称状压 DP）是利用整型的二进制位来紧凑表示离散集合的选取状态（通常 \(N \le 20\)）的高阶 DP 技术。它将指数级组合状态压缩至单个整型变量中，极大加速了状态的转移、判重与记忆化。
1. 集合状态表示与位运算原子操作¶
设全集为 \(U = \{0, 1, 2, \dots, n - 1\}\)，任意子集 \(S \subseteq U\) 均可唯一映射为一个 \(n\) 位的非负整数 \(mask \in [0, 2^n - 1]\)，其中第 \(i\) 位为 \(1\) 表示元素 \(i\) 被选入集合中。
高频位运算速查¶
| 操作目标 | 位运算表达式 | 含义解释 |
|---|---|---|
| 判断元素存在 | (mask >> i) & 1 |
检查第 \(i\) 位是否为 1 |
| 添加元素 | mask | (1 << i) |
将第 \(i\) 位置为 1 |
| 删除元素 | mask & ~(1 << i) |
将第 \(i\) 位置为 0 |
| 翻转元素状态 | mask ^ (1 << i) |
0 变 1，1 变 0 |
| 提取最低位 1 | mask & (-mask) |
提取 lowbit（最低非零位） |
| 清除最低位 1 | mask & (mask - 1) |
消去最低位的 1 |
| 集合大小 | __builtin_popcount(mask) |
统计二进制中 1 的个数 |
| 全集掩码 | (1 << n) - 1 |
\(n\) 位全部置 1 |
2. 子集遍历核心技巧与 \(\mathcal{O}(3^n)\) 复杂度严格证明¶
在许多划分与拼装问题中，需要对每个状态 \(mask\) 枚举它的所有非空子集 \(sub\)。
2.1 高效子集枚举代码¶
// 遍历 mask 的全部非空子集 sub (按降序排列)
for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
// sub 必定是 mask 的严格子集
}
- 核心机理：
sub - 1会将 \(sub\) 最低位的 \(1\) 翻转为 \(0\)，并将其后的所有 \(0\) 翻转为 \(1\)；随后通过& mask，强制屏蔽掉那些不属于母集合 \(mask\) 的多余位，从而在不遗漏任何子集的前提下步进到下一个合法子集。
2.2 复杂度证明：二项式定理与 \(\mathcal{O}(3^n)\)¶
表面上看，外层枚举 \(mask\) 有 \(2^n\) 种可能，内层枚举子集又有 \(2^n\) 种可能，总复杂度容易被误判为 \(\mathcal{O}(4^n)\)。 然而，并非所有 \(mask\) 都有 \(2^n\) 个子集！
严格数学证明¶
设母集合 \(mask\) 中包含 \(k\) 个元素（即有 \(k\) 个二进制位为 1），其子集数量恰好为 \(2^k\)。 在所有 \(2^n\) 个状态中，大小为 \(k\) 的集合数量为二项式系数 \(\binom{n}{k}\)。因此全状态子集遍历的总操作次数为：
根据二项式定理 \((x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k\)，令 \(x = 1, y = 2\)：
总时间复杂度是严格的 \(\mathcal{O}(3^n)\)，这对于 \(n \approx 12 \sim 15\) 的数据规模而言极具实战杀伤力！
3. 旅行商问题 (TSP) 状态机模型¶
给定 \(n\) 个城市及彼此间的距离矩阵 \(dist[u][v]\)，求解访问完所有城市且每个城市恰好访问一次的最短路径。
状态定义与转移¶
- 状态设计：定义 \(dp[mask][u]\) 表示已经访问过的城市集合为 \(mask\)，且当前所处的最后一个城市为 \(u\) 的最短路径长度；
- 状态转移方程：枚举下一个即将访问的城市 \(v\)（需满足 \((mask >> v) \& 1 == 0\)）：
#include <vector>
#include <algorithm>
const int INF = 1e9;
int tsp(int n, const std::vector<std::vector<int>>& dist) {
// dp[mask][u]
std::vector<std::vector<int>> dp(1 << n, std::vector<int>(n, INF));
// 起点初始化 (假设从城市 0 出发)
dp[1 << 0][0] = 0;
for (int mask = 1; mask < (1 << n); ++mask) {
for (int u = 0; u < n; ++u) {
if (dp[mask][u] >= INF) continue;
// 寻找下一个未访问的城市 v
for (int v = 0; v < n; ++v) {
if (!(mask & (1 << v))) {
int next_mask = mask | (1 << v);
dp[next_mask][v] = std::min(dp[next_mask][v], dp[mask][u] + dist[u][v]);
}
}
}
}
int ans = INF;
int full_mask = (1 << n) - 1;
for (int u = 0; u < n; ++u) {
ans = std::min(ans, dp[full_mask][u]);
}
return ans;
}
- 时间复杂度：\(\mathcal{O}(n^2 \cdot 2^n)\)
- 空间复杂度：\(\mathcal{O}(n \cdot 2^n)\)
4. LeetCode 经典真题精选与题解提示¶
-
LeetCode 847 - 访问所有节点的最短路径 (Shortest Path Visiting All Nodes)
困难提示
状压 + 双重 BFS。
- 图中有环且允许重复经过节点。
- 状态由二元组
(u, mask)唯一标识：当前在节点 \(u\) 且已访问集合为 \(mask\)。 - 由于边权均为 1，将所有单点
(i, 1 << i)同时入队作为多源起点，运行 BFS，首次弹出mask == (1 << n) - 1的步数即为全局最短步数。
-
LeetCode 943 - 最短超串 (Find the Shortest Superstring)
困难提示
字符串重叠度转化为有向图 TSP。
- 预处理两两字符串 \(S_i\) 与 \(S_j\) 拼接时能重叠的最大字符数作为图的权值。
- 运行标准状压 TSP 求出重叠字符最多的遍历顺序，最后通过记录的转移前驱路径还原拼接出的最短超串。
-
LeetCode 698 - 划分为k个相等的子集 (Partition to K Equal Sum Subsets)
中等提示
状压记忆化搜索 + 贪心剪枝。
- 目标是拼出 \(k\) 个和为 \(target\) 的桶。
- 状态定义：
dp[mask]记录选入集合 \(mask\) 时的当前未满桶余数current_sum % target。记忆化搜索避免重复搜索无效状态；降序排序优先处理大数可极大加速剪枝。
-
LeetCode 1655 - 分配重复整数 (Distribute Repeating Integers)
困难提示
顾客集合子集枚举 \(\mathcal{O}(3^m)\)。
- 顾客数量 \(m \le 10\)，状态压缩 \(mask \in [0, 2^m)\) 表示已被满足的顾客子集。
- 预处理每个子集所需要的总整数数量；
- 外层枚举可用的频次数字，内层按
for (int sub = mask; sub; sub = (sub - 1) & mask)枚举当前数字能够打包满足的新顾客子集。严格 \(\mathcal{O}(n \cdot 3^m)\)。
-
LeetCode 1349 - 参加考试的最大学生数 (Maximum Students Taking Exam)
困难提示
行间不冲突状压 DP。
- 考试座位受限于本行不能相邻、左前与右前不能看抄。
- 每一行可以容纳的考生分布压缩为一个二进制掩码；
- \(dp[i][mask]\) 表示第 \(i\) 行状态为 \(mask\) 时前 \(i\) 行的最大容纳学生数，仅依赖第 \(i-1\) 行的不冲突掩码进行状态转移。