基于经典“旅行商问题 TSP”，利用整数二进制按位遮罩（Mask）来表示和转移集合状态
对于排列组合类问题，我们常需要记录一个集合中包含哪些元素。若使用普通容器保存，状态很难设计递推。状态压缩动态规划巧妙利用二进制整数的位来压缩存储集合状态。
设有 $N$ 个城市，旅行商要从城市 0 出发，遍历所有城市恰好一次并回到 0，求最短环路。
我们用一个整数 mask 表示已访问城市的集合，其第 $i$ 位为 1 代表城市 $i$ 已访问，0 代表未访问（例如：0101（十进制 5）代表访问了城市 0 和 2）。
dp[mask][u] 表示当前访问过的城市集合为 mask，且当前停留在城市 $u$ 的最短路径。状态转移方程为：
其物理意义为：在到达 $u$ 之前，旅行商已经访问了集合中除了 $u$ 以外的所有城市（即 $mask \oplus (1 \ll u)$），且上一步停留在城市 $v$；我们枚举所有可能的上一跳城市 $v$，加上 $v \to u$ 的边权，取最小值。
| mask | 二进制 | 城市 0 | 城市 1 | 城市 2 | 城市 3 |
|---|
void tspDP() {
// dp[mask][u] 初始为 INF, dp[1][0] = 0 (起点为城市 0)
for (int mask = 1; mask < (1 << n); mask++) { // 1. 枚举所有压缩集合状态
for (int u = 0; u < n; u++) {
if (!(mask & (1 << u))) continue; // 2. u 必须存在于集合中！
int prev_mask = mask ^ (1 << u); // 3. 剔除 u 得到的前置状态
for (int v = 0; v < n; v++) {
if (prev_mask & (1 << v)) { // 4. 候选点 v 必须存在于 prev_mask
dp[mask][u] = min(dp[mask][u], dp[prev_mask][v] + dist[v][u]);
}
}
}
}
}