状态压缩 DP：旅行商与覆盖问题
hard动态规划状态压缩位运算
核心思想
用整数的二进制位表示集合状态，集合大小为 n，状态数为 2^n。
常见操作：
state | (1 << i)：将第 i 位置 1（加入集合）state & ~(1 << i)：将第 i 位置 0（移除集合）(state >> i) & 1：检查第 i 位是否为 1state == (1 << n) - 1：是否所有位都为 1（集合已满）
最短路径访问所有节点（LeetCode 847）
图中 n 个节点（n≤12），求从任意节点出发访问所有节点的最短路径长度：
BFS + 状态压缩：(node, visited) 为状态：
public int shortestPathLength(int[][] graph) {
int n = graph.length, full = (1 << n) - 1;
Queue<int[]> queue = new LinkedList<>(); // [node, state, dist]
boolean[][] visited = new boolean[n][1 << n];
for (int i = 0; i < n; i++) {
queue.offer(new int[]{i, 1 << i, 0});
visited[i][1 << i] = true;
}
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int node = cur[0], state = cur[1], dist = cur[2];
if (state == full) return dist;
for (int next : graph[node]) {
int nextState = state | (1 << next);
if (!visited[next][nextState]) {
visited[next][nextState] = true;
queue.offer(new int[]{next, nextState, dist + 1});
}
}
}
return -1;
}
旅行售货员问题（TSP）
访问 n 个城市恰好一次并回到起点，求最短路程（经典 n≤20）：
dp[mask][i] = 已访问的城市集合为 mask，当前在城市 i 的最短距离：
public int tsp(int[][] dist) {
int n = dist.length, full = (1 << n) - 1;
int[][] dp = new int[1 << n][n];
for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE / 2);
dp[1][0] = 0; // 从城市 0 出发
for (int mask = 1; mask < (1 << n); mask++) {
for (int u = 0; u < n; u++) {
if ((mask & (1 << u)) == 0 || dp[mask][u] == Integer.MAX_VALUE / 2) continue;
for (int v = 0; v < n; v++) {
if ((mask & (1 << v)) != 0) continue; // 已访问
int nextMask = mask | (1 << v);
dp[nextMask][v] = Math.min(dp[nextMask][v], dp[mask][u] + dist[u][v]);
}
}
}
int ans = Integer.MAX_VALUE;
for (int u = 1; u < n; u++) // 回到城市 0
ans = Math.min(ans, dp[full][u] + dist[u][0]);
return ans;
}
蒙德里安的梦想（格子染色压缩DP）
m×n 格子用 1×2 横和竖的骨牌铺满，方案总数（m,n≤11）：
使用按列压缩：枚举上一列横出状态，DFS 填充竖骨牌：
long[][] dp; // dp[i][j]: 第 i 列状态为 j 的方案数
boolean[] valid; // valid[j]: 状态 j 能否被竖着两个 1×1 填满（无奇数连续0）
// 具体实现需预处理 valid[] 并枚举列间兼容状态，篇幅略
总结
| 应用 | 状态含义 | 时间复杂度 |
|---|---|---|
| 访问所有节点最短路径 | (已访问集合, 当前节点) | O(2^n × n²) |
| 旅行商（TSP） | (已访问集合, 当前节点) | O(2^n × n²) |
| 骨牌铺满 | (当前列向右凸出的状态) | O(2^m × n × m) |
适用条件：状态中有一个集合，且集合大小 n ≤ 20（通常 ≤ 12 较实用）。