有些状态本质上是"一个集合"——用一个整数的每一位代表"某个元素在不在集合里"，把集合压缩进一个数字，直接当数组下标。
有些问题的"状态"，本质上是"一组元素里，哪些被选中了、哪些没有"——比如"这几个城市有没有被访问过"、"这几个物品有没有被选中"。如果元素个数不多（一般在 20 个以内），可以把整个"选择情况"压缩成一个二进制数：第 i 位是 1 表示第 i 个元素被选中，是 0 表示没被选中。这样一来，原本需要一整个数组才能描述的"集合状态"，就能直接当成一个整数，用作 dp 数组的下标——这就是状态压缩 DP（简称状压 DP）。
以 4 个元素（编号 0~3）为例，用一个 4 位的二进制数表示"这 4 个元素各自在不在集合里"：
1101（十进制 13）表示"城市 0、2、3 已经访问过，城市 1 还没有"。常用的位运算技巧：state >> i & 1 判断第 i 位是不是 1；state | (1<<i) 把第 i 位设成 1（添加元素 i）。旅行商问题（Travelling Salesman Problem）：有 n 个城市，从城市 0 出发，要访问其余所有城市各恰好一次，最后回到城市 0，求最短的总路程。朴素想法是枚举所有访问顺序（n! 种排列），状压 DP 能把这个问题优化到 O(2ⁿ × n²)。
状态定义：dp[state][i] 表示"已经访问过 state 这个集合里的所有城市，当前正好停在城市 i"时，走过的最短路程。转移方程：
dp[state | (1<<j)][j] = min( dp[state | (1<<j)][j], dp[state][i] + dist[i][j] )
枚举当前已经访问的集合 state、当前停留的城市 i（要求 i 在 state 里），再枚举一个还没访问过的城市 j（j 不在 state 里）——从 i 走到 j，更新"访问集合变成 state 加上 j、停在 j"这个新状态。
4 个城市（0、1、2、3），距离矩阵如下：
| dist | 城市 0 | 城市 1 | 城市 2 | 城市 3 |
|---|---|---|---|---|
| 城市 0 | 0 | 10 | 15 | 20 |
| 城市 1 | 10 | 0 | 35 | 25 |
| 城市 2 | 15 | 35 | 0 | 30 |
| 城市 3 | 20 | 25 | 30 | 0 |
| state（二进制） | 已访问的城市 | 当前所在城市 | dp 值 |
|---|---|---|---|
| 0001 | {0} | 0 | 0（起点） |
| 0011 | {0,1} | 1 | 0 + dist[0][1] = 10 |
| 1011 | {0,1,3} | 3 | 10 + dist[1][3] = 35 |
| 1111 | {0,1,2,3} | 2 | 35 + dist[3][2] = 65 |
| 全部城市访问完毕，回到起点：65 + dist[2][0] = 65 + 15 = 80 | |||
0 → 1 → 3 → 2 → 0，总路程 10+25+30+15=80。状压 DP 会同时计算所有 state 和 i 的组合（16 个 state × 4 个城市），这里只展示了最终得到最优解的那一条路径；实际运行时，另一条路径 0→2→3→1→0（方向相反）算出的也是 80，说明这两条路径其实是同一个环形路线的两个方向，distance 相同并不意外。真正的答案要在所有 dp[1111][i] + dist[i][0] 里取最小值，本节的例子里，i=1、i=2 两种都能取到 80，是当前数据下的最优解。| 1 | int dist[MAXCITY][MAXCITY], dp[1 << MAXCITY][MAXCITY], n; |
| 2 | |
| 3 | int TSP() |
| 4 | { |
| 5 | memset(dp, 0x3f, sizeof(dp)); // 全部初始化成"正无穷" |
| 6 | dp[1][0] = 0; // ★ 只访问了城市 0（state=0001），停在城市 0，代价为 0 |
| 7 | |
| 8 | for (int state = 1; state < (1 << n); state++) // ★ 枚举所有子集 |
| 9 | for (int i = 0; i < n; i++) |
| 10 | { |
| 11 | if (!(state >> i & 1) || dp[state][i] >= 0x3f3f3f3f) continue; // i 不在 state 里，或这个状态本来就不可达，跳过 |
| 12 | for (int j = 0; j < n; j++) |
| 13 | { |
| 14 | if (state >> j & 1) continue; // j 已经在 state 里了，不能重复访问 |
| 15 | int next_state = state | (1 << j); |
| 16 | dp[next_state][j] = min(dp[next_state][j], dp[state][i] + dist[i][j]); |
| 17 | } |
| 18 | } |
| 19 | |
| 20 | int full = (1 << n) - 1, ans = 0x3f3f3f3f; |
| 21 | for (int i = 0; i < n; i++) // ★ 所有城市都访问完后，加上"回到起点"的这一段 |
| 22 | ans = min(ans, dp[full][i] + dist[i][0]); |
| 23 | return ans; |
| 24 | } |
dp[1 << MAXCITY][MAXCITY] 里的第一维大小是 2ⁿ——每一个可能的"访问集合"都对应数组的一个下标，而不是像普通数组那样按 0,1,2,3... 顺序排列。第 8 行 state 从 1 遍历到 2ⁿ-1，恰好覆盖了"城市 0~n-1"所有可能的子集。状态数是 O(2ⁿ × n)，每个状态转移要枚举下一个城市 j，O(n)。总时间复杂度 O(2ⁿ × n²)——比 O(n!) 的暴力枚举快得多，但 2ⁿ 依然是指数级增长，n 一般不能超过 20 左右。
n=20 时 2ⁿ 已经超过 100 万，n=25 就超过 3000 万，再往上内存和时间都吃不消。状压 DP 只适合"集合规模较小"的场景，如果 n 达到几十甚至上百，需要换别的方法。state >> i & 1 里，>> 和 & 的优先级低于 ==、< 这些比较运算符，如果写成 state >> i & 1 == 0，会被解析成 state >> i & (1==0)（先算 1==0 得到 false），完全不是想要的结果。需要的话给整个位运算表达式加上括号：(state >> i & 1) == 0。i"的代价，最后还要在第 21～22 行手动加上 dist[i][0] 这一段"回程"的距离，才是完整的环形路程。如果题目不要求回到起点（开放式路径），则不需要这一步，直接取 dp[full][i] 的最小值即可。