旅行商 TSP（状压 DP）
动态规划 · 集合当下标 · Held-Karp
n! 条路线，怎么剪
推销员要走遍 n 座城市各一次、回到起点，求最短回路——旅行商问题。暴力枚举全排列 O(n!)：20 城就是 2.4×10¹⁸ 条路线。可仔细想：走到半路时，决定未来的只有两件事——去过哪些城（不在乎顺序！）和现在人在哪。不同顺序、同一批城、同一个落脚点的路线，只需要留最短的那条。
把集合压进一个整数
「去过哪些城」是个集合——用二进制 mask 压缩：第 i 位为 1 表示城 i 已访问。状态 dp[mask][i] = 已访问 mask、现在在城 i 的最短路程，转移时枚举上一站 j：dp[mask][i] = min (dp[mask∖{i}][j] + d[j][i])。下表 8 行就是含起点的全部 mask（二进制行标），逐格点亮、黄格 = 胜出的前置状态；填到全集行后，补上回起点的边取 min。右侧代码随每一步同步高亮。
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0001 | 0 | |||
| 0011 | ||||
| 0101 | ||||
| 0111 | ||||
| 1001 | ||||
| 1011 | ||||
| 1101 | ||||
| 1111 |
4 座城市各访问一次回到起点 0，求最短回路。全排列是 O(n!)；状压 DP 的洞察：走到半路，重要的只有「去过哪些城」和「现在在哪」——把集合压成二进制 mask 当行下标：dp[mask][i]。起点 dp[0001][0] = 0
1function tsp(d: number[][]): number {
2 const n = d.length, FULL = (1 << n) - 1;
3 const dp = Array.from({ length: 1 << n }, () => new Array(n).fill(Infinity));
4 dp[1][0] = 0; // 从城 0 出发
5 for (let mask = 3; mask <= FULL; mask++) {
6 if (!(mask & 1)) continue; // 必含起点
7 for (let i = 1; i < n; i++) {
8 if (!(mask & (1 << i))) continue;
9 const prev = mask ^ (1 << i); // 去掉 i 的前置集合
10 for (let j = 0; j < n; j++) // 上一站 j
11 if (prev & (1 << j))
12 dp[mask][i] = Math.min(dp[mask][i], dp[prev][j] + d[j][i]);
13 }
14 }
15 let best = Infinity;
16 for (let i = 1; i < n; i++) // 回到起点收尾
17 best = Math.min(best, dp[FULL][i] + d[i][0]);
18 return best;
19}
距离4 城对称矩阵（见代码）
状态数2ⁿ·n = 64
1 / 15
状压 DP 的边界与家族
复杂度：状态 2ⁿ·n 个、每个转移 O(n) → O(2ⁿ·n²)——从 n! 到指数，是巨大的降维。
实用上限：n ≈ 20（约 4 亿次运算）；再大交给近似/启发式（最近邻、2-opt、LKH）。
填表序：mask 从小到大天然满足拓扑序——子集永远先于超集就绪。
家族：子集枚举 DP（3ⁿ）、轮廓线 DP（棋盘覆盖）、集合划分——「集合当下标」一脉相承。
实用上限：n ≈ 20（约 4 亿次运算）；再大交给近似/启发式（最近邻、2-opt、LKH）。
填表序：mask 从小到大天然满足拓扑序——子集永远先于超集就绪。
家族：子集枚举 DP（3ⁿ）、轮廓线 DP（棋盘覆盖）、集合划分——「集合当下标」一脉相承。
至此 DP 大类八页集齐三种状态设计：序列前缀（LIS/LCS）、区间（石子合并）、集合（本页）——动态规划的想象力，全在「状态怎么定义」这一步。