1962年，Michael Held和Richard Karp在《Journal of the Society for Industrial and Applied Mathematics》上发表了一篇论文，提出了用动态规划求解旅行商问题（TSP）的算法。这个算法的时间复杂度是 $O(n^2 \cdot 2^n)$——虽然仍然是指数级，但相比暴力枚举的 $O(n!)$，已经是一个巨大的飞跃。这个算法的核心思想，正是后来被称为"状态压缩动态规划"（Bitmask DP / State Compression DP）的开山之作。
状态压缩DP是一种将集合状态压缩为整数的技术。当问题涉及"选择某些元素"或"访问某些节点"时，传统方法需要用数组或集合来记录状态，而状态压缩DP则用一个整数的二进制位来表示——第 $i$ 位为1表示选中，为0表示未选中。这种表示方法不仅节省空间，还能利用位运算实现高效的状态转移。掌握这一技术，意味着你能优雅地解决旅行商问题变种、集合划分、任务分配、排列组合等经典难题。
状态压缩的核心思想：一个整数就是一个集合
假设有5个城市，编号0到4。要表示"已访问城市0、2、4"这个状态，传统方法可能需要一个布尔数组 visited = [true, false, true, false, true]。但在状态压缩DP中，这个状态只需要一个整数：
这个二进制数的第0、2、4位为1，恰好对应被访问的城市。状态转移也变得极其简洁：
- 访问城市1：
state | (1 << 1)=10011 | 00010=10111= 23 - 离开城市2：
state & ~(1 << 2)=10011 & 11011=10001= 17 - 检查城市4是否已访问：
(state >> 4) & 1=(19 >> 4) & 1= 1（已访问） - 统计已访问城市数：
Integer.bitCount(state)= 3
这种表示方法的威力在于：$n$ 个元素的所有子集（共 $2^n$ 个）可以用 $0$ 到 $2^n - 1$ 的整数完美表示。整数天然有序、可索引、支持高效位运算——这些特性使得状态压缩DP成为解决组合优化问题的利器。
graph LR
subgraph "状态压缩表示"
A["集合 {0, 2, 4}"] --> B["二进制 10011"]
B --> C["十进制 19"]
end
subgraph "位运算操作"
D["添加元素1: 19 | 2 = 23"]
E["移除元素2: 19 & ~4 = 17"]
F["检查元素4: 19 >> 4 & 1 = 1"]
end
C --> D
C --> E
C --> F
位运算基础：状态压缩的工具箱
在深入状态压缩DP之前，必须熟练掌握以下位运算操作：
基本操作
int state = 0; // 空集
// 添加元素i到集合
state |= (1 << i); // state = state | (1 << i)
// 从集合中移除元素i
state &= ~(1 << i); // state = state & ~(1 << i)
// 检查元素i是否在集合中
boolean contains = ((state >> i) & 1) == 1;
// 或者
boolean contains = (state & (1 << i)) != 0;
// 切换元素i的状态（在集合中则移除，不在则添加）
state ^= (1 << i);
// 统计集合中元素个数
int count = Integer.bitCount(state);
// 获取集合的大小（元素个数上限）
int n = 5;
int fullState = (1 << n) - 1; // 11111 = 31，表示全集
枚举子集
状态压缩DP中经常需要枚举某个状态的所有子集，有一个经典技巧：
// 枚举state的所有非空子集
for (int sub = state; sub > 0; sub = (sub - 1) & state) {
// sub是state的一个子集
// 处理子集...
}
// 空集需要单独处理（如果需要）
这个技巧的时间复杂度是 $O(3^n)$ 而不是朴素的 $O(4^n)$，因为它直接跳过了不可能的子集。
枚举所有状态
int n = 5; // 元素个数
for (int state = 0; state < (1 << n); state++) {
// state代表一个子集
for (int i = 0; i < n; i++) {
if ((state & (1 << i)) != 0) {
// 元素i在当前子集中
}
}
}
状态压缩DP的经典模式
状态压缩DP的题目虽然千变万化，但核心模式只有几种：
模式一：旅行商问题（TSP）模式
问题特征：求访问所有节点/元素的最优路径或最小代价。
状态定义：dp[state][last] 表示已访问状态为 state，最后访问的元素是 last 时的最优解。
状态转移：
$$dp[state][last] = \min_{prev \in state, prev \neq last} \{dp[state \setminus \{last\}][prev] + cost(prev, last)\}$$时间复杂度：$O(n^2 \cdot 2^n)$
模式二：集合划分模式
问题特征：将元素划分为若干子集，满足特定条件。
状态定义：dp[state] 表示已使用的元素集合为 state 时的最优解或可行性。
状态转移：枚举下一个要加入的元素或子集。
时间复杂度：$O(n \cdot 2^n)$ 或 $O(3^n)$
模式三：按序填充模式
问题特征：按某种顺序填充位置，每个位置的选择依赖于之前的选择。
状态定义：dp[state] 或 dp[state][pos] 表示已选择元素为 state 时的最优解。
状态转移：根据当前位置的可选元素进行转移。
LeetCode经典题目详解
847. 访问所有节点的最短路径
题目描述：给定一个无向连通图，求访问所有节点的最短路径长度。可以从任意节点出发，可以多次访问同一节点，可以重用边。
解题思路：这是典型的TSP模式问题。状态定义为 (当前节点, 已访问节点集合)，使用BFS进行状态转移。
class Solution {
public int shortestPathLength(int[][] graph) {
int n = graph.length;
int fullMask = (1 << n) - 1;
// BFS队列：(当前节点, 访问状态)
Queue<int[]> queue = new LinkedList<>();
// 记录已访问的状态
Set<String> visited = new HashSet<>();
// 从每个节点出发
for (int i = 0; i < n; i++) {
queue.offer(new int[]{i, 1 << i});
visited.add(i + "," + (1 << i));
}
int step = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] curr = queue.poll();
int node = curr[0];
int mask = curr[1];
if (mask == fullMask) {
return step;
}
for (int next : graph[node]) {
int newMask = mask | (1 << next);
String key = next + "," + newMask;
if (!visited.contains(key)) {
visited.add(key);
queue.offer(new int[]{next, newMask});
}
}
}
step++;
}
return -1;
}
}
复杂度分析：
- 时间复杂度：$O(n \cdot 2^n)$，每个状态最多访问一次
- 空间复杂度：$O(n \cdot 2^n)$，用于存储访问状态
943. 最短超级串
题目描述：给定字符串数组，找到包含所有字符串作为子串的最短字符串。
解题思路：这本质上是TSP问题的一个变种。将每个字符串看作节点，字符串 $i$ 接在字符串 $j$ 后面需要额外增加的字符数就是边权。
class Solution {
public String shortestSuperstring(String[] words) {
int n = words.length;
// 预处理：计算words[i]接在words[j]后面需要增加的字符数
int[][] cost = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) continue;
cost[i][j] = getOverlapCost(words[i], words[j]);
}
}
// dp[mask][last] = (最小长度, 对应字符串)
int[][] dp = new int[1 << n][n];
int[][] parent = new int[1 << n][n];
for (int mask = 0; mask < (1 << n); mask++) {
Arrays.fill(dp[mask], Integer.MAX_VALUE / 2);
Arrays.fill(parent[mask], -1);
}
// 初始状态：只选一个字符串
for (int i = 0; i < n; i++) {
dp[1 << i][i] = words[i].length();
}
// 状态转移
for (int mask = 1; mask < (1 << n); mask++) {
for (int last = 0; last < n; last++) {
if ((mask & (1 << last)) == 0) continue;
int prevMask = mask ^ (1 << last);
if (prevMask == 0) continue;
for (int prev = 0; prev < n; prev++) {
if ((prevMask & (1 << prev)) == 0) continue;
if (dp[prevMask][prev] + cost[prev][last] < dp[mask][last]) {
dp[mask][last] = dp[prevMask][prev] + cost[prev][last];
parent[mask][last] = prev;
}
}
}
}
// 找最优终点
int last = 0;
int fullMask = (1 << n) - 1;
for (int i = 1; i < n; i++) {
if (dp[fullMask][i] < dp[fullMask][last]) {
last = i;
}
}
// 回溯构造答案
int mask = fullMask;
List<Integer> path = new ArrayList<>();
while (mask > 0) {
path.add(last);
int prev = parent[mask][last];
mask ^= (1 << last);
last = prev;
}
Collections.reverse(path);
// 构造结果字符串
StringBuilder sb = new StringBuilder(words[path.get(0)]);
for (int i = 1; i < path.size(); i++) {
int prev = path.get(i - 1);
int curr = path.get(i);
int overlap = words[prev].length() - cost[prev][curr];
sb.append(words[curr].substring(overlap));
}
return sb.toString();
}
private int getOverlapCost(String a, String b) {
int maxOverlap = 0;
for (int len = Math.min(a.length(), b.length()); len > 0; len--) {
if (a.substring(a.length() - len).equals(b.substring(0, len))) {
maxOverlap = len;
break;
}
}
return b.length() - maxOverlap;
}
}
698. 划分为k个相等的子集
题目描述：给定整数数组和整数k，判断是否能将数组划分为k个和相等的非空子集。
解题思路：这是集合划分模式的经典问题。使用状态压缩表示已使用的元素，动态记录当前正在填充的子集的当前和。
class Solution {
public boolean canPartitionKSubsets(int[] nums, int k) {
int sum = 0;
for (int num : nums) sum += num;
if (sum % k != 0) return false;
int target = sum / k;
Arrays.sort(nums);
// 从大到小排序，提前剪枝
int n = nums.length;
if (nums[n - 1] > target) return false;
int fullMask = (1 << n) - 1;
// dp[mask] = 当前已使用mask状态下，正在填充的子集的当前和
// -1 表示不可达
int[] dp = new int[1 << n];
Arrays.fill(dp, -1);
dp[0] = 0;
for (int mask = 0; mask < (1 << n); mask++) {
if (dp[mask] == -1) continue;
for (int i = 0; i < n; i++) {
// 如果第i个元素已被使用，跳过
if ((mask & (1 << i)) != 0) continue;
int newSum = dp[mask] + nums[i];
if (newSum <= target) {
int newMask = mask | (1 << i);
// 如果恰好填满，开始新的子集
dp[newMask] = (newSum == target) ? 0 : newSum;
}
}
}
return dp[fullMask] == 0;
}
}
复杂度分析：
- 时间复杂度：$O(n \cdot 2^n)$
- 空间复杂度：$O(2^n)$
1349. 参加考试的最大学生数
题目描述：给定教室座位图，学生不能作弊（左前、右前、左、右不能有人），求最多能安排多少学生。
解题思路：逐行处理，每行的安排只受上一行影响。状态定义为当前行的座位安排。
class Solution {
public int maxStudents(char[][] seats) {
int m = seats.length;
int n = seats[0].length;
// 将每行转换为有效座位掩码
int[] rowMasks = new int[m];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (seats[i][j] == '.') {
rowMasks[i] |= (1 << j);
}
}
}
// dp[i][mask] = 第i行状态为mask时的最大学生数
int[][] dp = new int[m + 1][1 << n];
for (int i = 1; i <= m; i++) {
int validMask = rowMasks[i - 1];
for (int mask = 0; mask < (1 << n); mask++) {
// 检查mask是否有效：
// 1. 只能放在有效座位上
// 2. 学生之间不能相邻
if ((mask & validMask) != mask) continue;
if ((mask & (mask >> 1)) != 0) continue; // 左右不能相邻
int students = Integer.bitCount(mask);
for (int prevMask = 0; prevMask < (1 << n); prevMask++) {
// 检查与上一行是否冲突
// 左前和右前不能有人
if ((mask & (prevMask >> 1)) != 0) continue;
if ((mask & (prevMask << 1)) != 0) continue;
dp[i][mask] = Math.max(dp[i][mask], dp[i - 1][prevMask] + students);
}
}
}
int result = 0;
for (int mask = 0; mask < (1 << n); mask++) {
result = Math.max(result, dp[m][mask]);
}
return result;
}
}
复杂度分析：
- 时间复杂度：$O(m \cdot 4^n)$
- 空间复杂度：$O(m \cdot 2^n)$
1434. 每个人戴不同帽子的方案数
题目描述：给定每个人喜欢的帽子列表，求所有人戴不同帽子的方案数（模 $10^9 + 7$）。
解题思路：这题的关键在于状态应该表示"已分配的人"，而不是"已分配的帽子"，因为帽子最多40种，人数最多10人。
class Solution {
private static final int MOD = 1_000_000_007;
public int numberWays(int[][] hats) {
int n = hats.length; // 人数
int fullMask = (1 << n) - 1;
// 建立帽子到人的映射
List<List<Integer>> hatToPeople = new ArrayList<>();
for (int i = 0; i <= 40; i++) {
hatToPeople.add(new ArrayList<>());
}
for (int person = 0; person < n; person++) {
for (int hat : hats[person]) {
hatToPeople.get(hat).add(person);
}
}
// dp[hat][mask] = 处理到第hat顶帽子时，分配状态为mask的方案数
int[][] dp = new int[41][1 << n];
dp[0][0] = 1;
for (int hat = 1; hat <= 40; hat++) {
// 先继承不选当前帽子的状态
for (int mask = 0; mask <= fullMask; mask++) {
dp[hat][mask] = dp[hat - 1][mask];
}
// 尝试将当前帽子分配给喜欢它的人
for (int mask = 0; mask <= fullMask; mask++) {
if (dp[hat - 1][mask] == 0) continue;
for (int person : hatToPeople.get(hat)) {
// 这个人还没分配帽子
if ((mask & (1 << person)) == 0) {
int newMask = mask | (1 << person);
dp[hat][newMask] = (dp[hat][newMask] + dp[hat - 1][mask]) % MOD;
}
}
}
}
return dp[40][fullMask];
}
}
复杂度分析：
- 时间复杂度：$O(40 \cdot 2^n \cdot n) = O(n \cdot 2^n)$
- 空间复杂度：$O(40 \cdot 2^n)$
1595. 连接两组点的最小代价
题目描述：两组点，需要用边将两组点完全连通，每组内的每个点至少有一条边连接到另一组，求最小总代价。
解题思路：第一组点逐个处理，用状态压缩记录第二组点的连接情况。最后对第二组未连接的点，贪心选择最小代价。
class Solution {
public int connectTwoGroups(List<List<Integer>> cost) {
int m = cost.size(); // 第一组点数
int n = cost.get(0).size(); // 第二组点数
int fullMask = (1 << n) - 1;
// 预处理：每个第二组点的最小连接代价
int[] minCost = new int[n];
Arrays.fill(minCost, Integer.MAX_VALUE);
for (int j = 0; j < n; j++) {
for (int i = 0; i < m; i++) {
minCost[j] = Math.min(minCost[j], cost.get(i).get(j));
}
}
// dp[i][mask] = 处理完第一组前i个点，第二组连接状态为mask的最小代价
int[][] dp = new int[m + 1][1 << n];
for (int[] row : dp) {
Arrays.fill(row, Integer.MAX_VALUE / 2);
}
dp[0][0] = 0;
for (int i = 1; i <= m; i++) {
for (int mask = 0; mask <= fullMask; mask++) {
if (dp[i - 1][mask] == Integer.MAX_VALUE / 2) continue;
// 尝试将第一组第i-1个点连接到第二组的任意点
for (int j = 0; j < n; j++) {
int newMask = mask | (1 << j);
int newCost = dp[i - 1][mask] + cost.get(i - 1).get(j);
dp[i][newMask] = Math.min(dp[i][newMask], newCost);
}
}
}
int result = Integer.MAX_VALUE;
for (int mask = 0; mask <= fullMask; mask++) {
int totalCost = dp[m][mask];
// 对于第二组未连接的点，贪心选择最小代价
for (int j = 0; j < n; j++) {
if ((mask & (1 << j)) == 0) {
totalCost += minCost[j];
}
}
result = Math.min(result, totalCost);
}
return result;
}
}
复杂度分析：
- 时间复杂度：$O(m \cdot n \cdot 2^n)$
- 空间复杂度：$O(m \cdot 2^n)$
464. 我能赢吗
题目描述：两个玩家轮流从1到maxChoosableInteger中选择一个数，累计和达到或超过desiredTotal者获胜。问先手是否能必胜。
解题思路：博弈论+状态压缩。用状态压缩记录已选的数，递归判断当前状态是否必胜。
class Solution {
public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
// 如果总和都达不到目标，没人能赢
int sum = maxChoosableInteger * (maxChoosableInteger + 1) / 2;
if (sum < desiredTotal) return false;
// 如果目标<=0，先手直接赢
if (desiredTotal <= 0) return true;
return dfs(desiredTotal, 0, maxChoosableInteger, new Boolean[1 << maxChoosableInteger]);
}
// state: 已选数字的状态，第i位为1表示数字i+1已选
private boolean dfs(int remaining, int state, int maxInt, Boolean[] memo) {
if (remaining <= 0) return false; // 上一个选手已经赢了
if (memo[state] != null) return memo[state];
for (int i = 1; i <= maxInt; i++) {
// 数字i还未被选
if ((state & (1 << (i - 1))) == 0) {
// 如果选了i能直接赢，或者对手在剩余状态下必输
if (i >= remaining || !dfs(remaining - i, state | (1 << (i - 1)), maxInt, memo)) {
memo[state] = true;
return true;
}
}
}
memo[state] = false;
return false;
}
}
复杂度分析：
- 时间复杂度：$O(2^n \cdot n)$
- 空间复杂度：$O(2^n)$
1659. 最大化网格幸福感
题目描述：在网格中放置内向者和外向者，相邻会影响幸福感，求最大总幸福感。
解题思路：按位置顺序填充，状态需要记录当前行前一格的填充情况以及上一行的填充情况。
class Solution {
private int m, n;
private int[][][][][] dp;
private static final int MOD = 1_000_000_007;
public int getMaxGridHappiness(int m, int n, int introvertsCount, int extrovertsCount) {
this.m = m;
this.n = n;
// dp[pos][prevRow][in][ex] = 最大幸福感
// prevRow是一个状态压缩，表示上一行的填充情况
// 0=空, 1=内向, 2=外向，用2位表示一个格子
dp = new int[m * n][1 << (2 * n)][introvertsCount + 1][extrovertsCount + 1];
for (int[][][][] d1 : dp) {
for (int[][][] d2 : d1) {
for (int[][] d3 : d2) {
for (int[] d4 : d3) {
Arrays.fill(d4, -1);
}
}
}
}
return dfs(0, 0, introvertsCount, extrovertsCount);
}
private int dfs(int pos, int prevRow, int in, int ex) {
if (pos == m * n) return 0;
if (dp[pos][prevRow][in][ex] != -1) return dp[pos][prevRow][in][ex];
int row = pos / n, col = pos % n;
int result = dfs(pos + 1, clearPosition(prevRow, col), in, ex); // 不放人
// 计算与左边和上边邻居的影响
int leftNeighbor = (col > 0) ? getPosition(prevRow, col - 1) : 0;
int upNeighbor = getPosition(prevRow, col);
// 放内向者
if (in > 0) {
int happiness = 120; // 内向者基础幸福感
happiness -= getNeighborCost(leftNeighbor, 1);
happiness -= getNeighborCost(upNeighbor, 1);
result = Math.max(result, happiness + dfs(pos + 1, setPosition(prevRow, col, 1), in - 1, ex));
}
// 放外向者
if (ex > 0) {
int happiness = 40; // 外向者基础幸福感
happiness += getNeighborCost(leftNeighbor, 2);
happiness += getNeighborCost(upNeighbor, 2);
result = Math.max(result, happiness + dfs(pos + 1, setPosition(prevRow, col, 2), in, ex - 1));
}
dp[pos][prevRow][in][ex] = result;
return result;
}
private int getPosition(int state, int col) {
return (state >> (2 * col)) & 3;
}
private int setPosition(int state, int col, int val) {
return (state & ~(3 << (2 * col))) | (val << (2 * col));
}
private int clearPosition(int state, int col) {
return state & ~(3 << (2 * col));
}
private int getNeighborCost(int neighbor, int myType) {
if (neighbor == 0) return 0;
int cost = 0;
// 邻居内向：-30，邻居外向：+20
cost += (neighbor == 1) ? -30 : 20;
// 我内向：-30，我外向：+20
cost += (myType == 1) ? -30 : 20;
return cost;
}
}
复杂度分析：
- 时间复杂度：$O(m \cdot n \cdot 3^n \cdot I \cdot E)$
- 空间复杂度：$O(m \cdot n \cdot 3^n \cdot I \cdot E)$
状态压缩DP的优化技巧
记忆化搜索 vs 递推
状态压缩DP既可以用递推实现，也可以用记忆化搜索。两种方式各有优劣：
递推：
- 优点：无需递归开销，空间可以优化
- 缺点：需要确定正确的遍历顺序
记忆化搜索：
- 优点：只计算需要的状态，避免无效计算
- 缺点：递归有开销
对于状态空间较大的问题，记忆化搜索通常更优，因为它可以跳过大量不可达状态。
状态压缩维度的选择
当问题涉及两维（如人和帽子、课程和学期）时，应该选择哪一维进行压缩？
原则是：压缩规模较小的一维。
例如在"每个人戴不同帽子"问题中，帽子有40种，人最多10个。如果用帽子状态压缩，状态空间是 $2^{40}$，不可接受；如果用人的状态压缩，状态空间是 $2^{10} = 1024$，完全可行。
子集枚举优化
当需要枚举某个状态的所有子集时，使用 (sub - 1) & state 技巧：
for (int sub = state; sub > 0; sub = (sub - 1) & state) {
// 处理子集sub
}
这个技巧确保只枚举有效子集，时间复杂度从 $O(2^n)$ 降到 $O(3^n)$。
空间优化
对于 $dp[state]$ 形式的状态定义，如果状态转移只依赖于更小状态的值，可以按状态值从小到大遍历，从而复用空间。
对于 $dp[state][last]$ 形式，可以用滚动数组优化空间。
状态压缩DP的适用场景
状态压缩DP适用于以下场景：
- 元素个数较少（通常 $n \leq 20$，有时可达 $25$）
- 问题涉及元素的选择/排列/划分
- 状态可以用"选/不选"的二进制表示
- 具有最优子结构
判断一道题是否适合用状态压缩DP，关键是看能否用整数表示状态，以及状态空间是否可接受。
总结
状态压缩DP将集合表示为整数，用位运算实现高效的状态转移，是解决组合优化问题的重要武器。从1962年Held-Karp算法诞生至今，这一技术已经在无数竞赛题目和实际应用中证明了其价值。
掌握状态压缩DP，需要：
- 熟练运用位运算操作
- 理解经典模式（TSP、集合划分、按序填充）
- 能够根据问题特点选择合适的状态定义
- 善用记忆化搜索优化空间
当你在LeetCode上看到题目涉及"选择某些元素"、“访问所有节点”、“划分为子集”，且元素个数不超过20时，状态压缩DP很可能就是解题的关键。
参考文献
- Held, M., & Karp, R. M. (1962). A Dynamic Programming Approach to Sequencing Problems. Journal of the Society for Industrial and Applied Mathematics, 10(1), 196-210.
- LeetCode Problem List - Bitmask: https://leetcode.com/problem-list/bitmask/
- USACO Guide - Bitmask DP: https://usaco.guide/gold/dp-bitmasks
- CP-Algorithms - Enumerating submasks of a bitmask: https://cp-algorithms.com/algebra/all-submasks.html
- LeetCode Discuss - Dynamic programming on subsets with examples: https://leetcode.com/discuss/general-discussion/1125779/
- GeeksforGeeks - Bitmasking and Dynamic Programming: https://www.geeksforgeeks.org/dsa/bitmasking-dynamic-programming-set-2-tsp/