快递员小明每天从站点出发，要给5个小区送快递——每个小区至少进一次，送完最后回到站点。他手里有一张地图，标着所有小区之间的距离。怎么走最短？他试过把所有顺序都算一遍：5个小区有120种走法，10个就是362万种，15个高达1.3万亿种，算到退休也算不完。 后来小明换了个思路：他不再记“完整路线”，只记两件事——哪些小区已经送过了（用一排开关灯表示）和我现在正站在哪个小区门口。每送完一家，就点亮对应的灯。这样一来，要处理的状态从天文数字的排列数骤降到“灯的组合数 × 小区数”，也就是 n·2^n 个。靠着这份“开关灯账本”，小明几分钟就能算出一条最优环城路线。 这就是状态压缩DP：用二进制位表示“集合”这一维度，再用一张二维表记录“当前集合 + 当前位置”的最优值，把旅行商问题（TSP）从指数爆炸的 n! 压缩到可处理的 n·2^n。这篇文章会顺着小明的送货故事，把问题建模、状态设计、转移方程、位运算优化和路径回溯完整走一遍。

岗位关联

状压DP是算法面试与工程优化中的高频硬技能。掌握TSP的完整建模与位运算技巧，能帮助你在物流调度、芯片布线、编译器状态机优化等场景中快速设计出高效方案，也是晋升资深算法工程师的必经阶梯。

目录
  1. 可视化演示
  2. 第一章：TSP问题定义——快递员的头疼清单
  3. 第二章：状态压缩思想——一排会说话的开关灯
  4. 第三章：DP状态设计——送货单上的二维账本
  5. 第四章：转移方程推导——把上一格的里程接力过来
  6. 第五章：位运算优化——拨开关的指尖技巧
  7. 第六章：路径回溯——让路线从账本里走出来
  8. 第七章：复杂度与应用——这笔买卖到底省了多少
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

状态压缩动态规划利用二进制位表示集合状态，将指数级状态空间压缩为可处理规模。本文以旅行商问题TSP为例讲解子集... 切换模式查看不同维度。

本节配有交互动效（进入视口后自动加载，约 3KB）。

状态压缩DP：核心原理 动态展示关键流程与数据流动 交互控件调节参数实时渲染 f(x) = transform(x) 核心概念的可视化呈现

第一章：TSP问题定义——快递员的头疼清单

这天站长把小明叫到办公室，递给他一张画了5个小区的任务单：“每个小区都要送到，从站点出发，最后回站点，你自己挑条最短的。”小明翻了翻地图，发现每两个小区之间都有一条直达的路。他心想：那还不简单？把所有走法都列出来比较一下不就行了。可当他试着列时，发现5个小区已经有120种顺序，6个就是720种，越列越心慌。

这就是旅行商问题（TSP）的由来：给定 n 个城市和两两之间的距离，找一条从起点出发、恰好访问每个城市一次、最后返回起点的最短回路。生活里它无处不在——快递派送、外卖骑手、工厂里机器人的钻孔顺序，全都是“怎么把一圈地方跑完最省力”的数学抽象。

朴素的做法就是小明最初的想法：枚举所有排列。第1个城市有 n 种选法，第2个有 n-1 种……乘起来就是全排列数。

小明后来才知道，TSP 属于 NP 完全问题：目前没有多项式时间算法，n 稍微一大，暴力枚举就会让计算机也“罢工”。小明的头疼不是没道理的——但他很快会发现，自己的“开关灯账本”远比想象中聪明。

T(n)=n×(n−1)×(n−2)×⋯×1=n!\displaystyle T(n) = n \times (n-1) \times (n-2) \times \cdots \times 1 = n!
  1. 第一站选择从起点出发后，第一个访问的城市有 n 个候选，这就是排列中的第一个因子。
    n\displaystyle n
  2. 逐站递减每确定一个城市，剩下的候选数就少一个，连续相乘得到所有路线的总数。
    n×(n−1)×⋯×1=n!\displaystyle n \times (n-1) \times \cdots \times 1 = n!

第二章：状态压缩思想——一排会说话的开关灯

小明想了一个省事的记法：他在站点墙上钉了一排开关灯，每个小区一盏。出发前全部熄灭；每送完一个小区，就把对应的灯点亮。“现在几盏灯亮着”就代表“哪些小区已经送过了”——至于先送谁后送谁，他暂时不管。这一排灯，就是“状态”。

在计算机里，这一排灯用一个二进制整数来表示，称为掩码 mask。比如 5 个城市时，二进制数 00111 表示“城市 0、1、2 已访问，城市 3、4 未访问”。每个二进制位要么是 0（灯灭）要么是 1（灯亮），恰好一一对应集合中元素的“在不在”。

这就是“状态压缩”的核心：原本一条路线要记录 n 个城市的先后顺序（n! 种排列），现在只需要记录“哪些城市去了”（2^n 种集合）。小明恍然大悟：灯的亮灭组合只有 2^n 种，比 n! 少太多了！至于“我现在在哪”，再单独用一列记下来即可——这就是下一章要展开的账本。

mask=(bn−1 bn−2 ⋯ b1 b0)2,bi∈{0,1}\displaystyle mask = (b_{n-1}\, b_{n-2}\, \cdots\, b_1\, b_0)_{2}, \quad b_i \in \{0, 1\}
  1. 位与城市编号二进制从右往左第 i 位，专门负责记录“城市 i 是否已访问”，约定 1 表示亮灯（已访问）。
    bi=(mask>>i)&1\displaystyle b_i = (mask >> i) \& 1
  2. 集合编码整个 mask 就是一个长度为 n 的 0/1 序列，共 2^n 种组合，恰好等于所有子集的数量。
    mask=∑i=0n−1bi×2i\displaystyle mask = \sum_{i=0}^{n-1} b_i \times 2^i

第三章：DP状态设计——送货单上的二维账本

小明把“开关灯面板”和“当前位置”结合起来，做成了一张二维送货单：行是灯的亮灭组合（mask），列是“我现在站在哪个小区门口”。每个格子记录一个数——在“这个灯组合 + 站在这个小区”的情况下，已经走过的最短里程。这张表，就是 DP 数组。

形式化定义：设 dp[mask][i] 表示“已经访问过的城市集合为 mask，且当前停在城市 i 时，走过的总路程的最小值”。其中 mask 的第 i 位必须是 1（因为人不可能站在没去过的城市）。

初始化也顺理成章：小明从站点（城市 0）出发，一辆车都还没跑，此时只有 dp[1][0] = 0，其他格子都是无穷大。换句话说，只有“1 号灯亮（只访问了城市 0）且站在城市 0”这个状态是合法的起点。最终要回答的问题，则是所有灯全亮（mask 全 1）后，从某个城市回到站点的最短回路——这一点在第四章结尾揭晓。

dp[mask][i]=min⁡{从起点出发，恰好访问 mask 中全部城市，最终停在 i 的最短路程}\displaystyle dp[mask][i] = \min\{\text{从起点出发，恰好访问 mask 中全部城市，最终停在 i 的最短路程}\}
  1. 状态两个维度第一维 mask 回答“去了哪”，第二维 i 回答“现在在哪”，两者缺一不可。
    dp[mask][i]\displaystyle dp[mask][i]
  2. 约束条件城市 i 必须已经在集合中，否则这个状态没有物理意义。
    i∈mask  ⟺  (mask>>i)&1=1\displaystyle i \in mask \iff (mask >> i) \& 1 = 1

第四章：转移方程推导——把上一格的里程接力过来

账本有了，怎么填？小明盯着 00111 这一行、站在城市 2 的那一格，突然想到：我上一站一定在某个“灯比现在少一盏”的状态里。比如 00101（城市 2 的灯还没亮）站在城市 0，再从 0 开车到 2，就得到了 00111 站在 2。所以这个格子的值，等于所有“少了城市 i 的灯、站在某个 j”的格子值，加上 j 到 i 的距离，再取最小值。

这就是状态转移方程——“拉”式写法：为了到达 (mask, i)，先退一步：把城市 i 从集合中“摘掉”，得到上一状态 (mask \ {i}, j)，然后从 j 走到 i。

小明的填表顺序也很讲究：只允许“灯少的行”去更新“灯多的行”，也就是 mask 按数值从小到大递推。因为去掉一个 1 之后 mask 一定变小，所以从小到大遍历 mask，能保证每次用到上一状态时它已经被算好了。最后答案藏在“全亮的灯”那一行：从某个城市 i 回到站点的最小回路。

dp[mask][i]=min⁡j∈mask, j≠i{dp[mask∖{i}][j]+dist[j][i]}\displaystyle dp[mask][i] = \min_{j \in mask,\ j \ne i} \left\{ dp[mask \setminus \{i\}][j] + dist[j][i] \right\}
公式通俗说明：整趟送货的最短里程 = 最后一站 i 的“全亮灯账本值” 加上 i 回站点的路。把所有可能的最后一站都比较一遍，最小的那个就是答案。
  1. 拆掉城市 i用异或运算把第 i 位从 1 变 0，表示“我还没到 i 时的集合”。
    mask∖{i}=mask ∧ ∼(1<<i)=mask  ⊕  (1<<i)\displaystyle mask \setminus \{i\} = mask \,\land\, \sim(1 << i) = mask \;\oplus\; (1 << i)
  2. 枚举前任城市 jj 必须是“去掉 i 之后的集合”里的城市，并且 j ≠ i，因为上一站不能是自己。
    j∈(mask∖{i})\displaystyle j \in (mask \setminus \{i\})
  3. 拼接里程把“到 j 为止的最短路程”加上“从 j 开到 i 的这一段路”，得到一条候选路线。
    dp[mask∖{i}][j]+dist[j][i]\displaystyle dp[mask \setminus \{i\}][j] + dist[j][i]
  4. 取最小对所有合法的 j 取一遍最小值，账本这一格就填好了。
    ans=min⁡i≠0{dp[(1<<n)−1][i]+dist[i][0]}\displaystyle ans = \min_{i \ne 0} \left\{ dp[(1<<n) - 1][i] + dist[i][0] \right\}

第五章：位运算优化——拨开关的指尖技巧

账本有了，填的时候还要频繁“拨开关”。小明发现，用二进制位运算来操作灯，比念叨“第几盏灯”快得多。他说到底只需要三招：开灯（把某个位置 1）、关灯（把某个位置 0）、查灯（看某个位置是 0 还是 1）。

小明靠着这三个“指尖动作”，把账本的每一格都填得飞快。需要注意的是，位运算在大多数编程语言里优先级低于算术运算但高于比较运算，写代码时尽量加括号，避免“拨错开关”。

mask∣(1<<i)开灯：把城市 i 标记为已访问\displaystyle mask \mid (1 << i) \quad \text{开灯：把城市 i 标记为已访问}
mask  &  ∼(1<<i)关灯：把城市 i 标记为未访问\displaystyle mask \;\&\; \sim(1 << i) \quad \text{关灯：把城市 i 标记为未访问}
(mask>>i)  &  1查灯：城市 i 是否在集合中\displaystyle (mask >> i) \;\&\; 1 \quad \text{查灯：城市 i 是否在集合中}
  1. 开灯（置 1）1 左移 i 位得到只在第 i 位是 1 的数，与 mask 做按位或，其他位保持不变，第 i 位必为 1。
    1<<i=2i\displaystyle 1 << i = 2^i
  2. 查灯（读位）把 mask 右移 i 位，让第 i 位落到最低位，再与 1 相与，得到 1 表示灯亮、0 表示灯灭。
    (mask>>i) & 1\displaystyle (mask >> i) \,\&\, 1
  3. 枚举子集在按 mask 递推时，经常需要枚举“某个 mask 的所有子集”，用 $sub = (sub-1) \,\&\, mask$ 可以从大到小不重不漏地扫过所有子集，且自动跳过不在 mask 中的位。
    sub=(sub−1)  &  mask\displaystyle sub = (sub - 1) \;\&\; mask

第六章：路径回溯——让路线从账本里走出来

账本填完了，小明看着“最短里程 24”这个数字，站长却问：“最短路线是哪条？”小明愣住了——账本只记录了最小值，没记录“这个值是怎么来的”。他这才意识到，光有 dp 表还不够，得把每一步的选择也存下来。

解决办法是再加一张“前驱表”：每当我们通过 dp[mask去掉i][j] + dist[j][i] 更新 dp[mask][i] 时，就把 j 记录到 prev[mask][i] 里。这样每个格子除了“最短值”，还多了一条“我从哪个城市来”的线索。

小明照着 prev 表一路倒推，很快拼出了完整路线：0 → 2 → 1 → 3 → 4 → 0。站长满意地点点头，小明也明白了：动态规划负责算“最优值”，回溯负责还原“最优解”——两者配合，才能把账本变成真正可以执行的送货路线。

prev[mask][i]=arg⁡min⁡j∈mask∖{i}{dp[mask∖{i}][j]+dist[j][i]}\displaystyle prev[mask][i] = \arg\min_{j \in mask \setminus \{i\}} \left\{ dp[mask \setminus \{i\}][j] + dist[j][i] \right\}
  1. 记录决策argmin 表示“让花括号里取到最小值的那个 j”，也就是最优路线里城市 i 的前一站。
    arg⁡min⁡j{dp[mask∖{i}][j]+dist[j][i]}\displaystyle \arg\min_j \{ dp[mask \setminus \{i\}][j] + dist[j][i] \}
  2. 从终点倒推找到最优答案对应的终点 i 后，通过 prev 一路向前翻，把城市逐个倒序吐出。
    i←prev[mask][i],mask←mask∖{i}\displaystyle i \leftarrow prev[mask][i], \quad mask \leftarrow mask \setminus \{i\}
  3. 反转路线倒推得到的是逆序，最后 reverse 一下，再补上起点 0，就得到完整回路。
    0→path[0]→path[1]→⋯→path[n−2]→0\displaystyle 0 \to path[0] \to path[1] \to \cdots \to path[n-2] \to 0

第七章：复杂度与应用——这笔买卖到底省了多少

现在，我们来算算小明的“开关灯账本”到底省了多少力气。暴力枚举需要列出 n! 条完整路线；状压 DP 的状态数是“灯的组合数 × 城市数”，即 n · 2^n。每个状态要枚举 n 个可能的上一站 j，所以总时间约为 n² · 2^n。

对比一下：n=20 时，20! 约为 2.4×10^{18}，而 20² × 2^{20} 约 4.2×10^8，足足省了十亿倍。小明这下放心了：15 个城市以内的精确最优解，普通笔记本也能秒出结果；更大的规模则交给遗传算法、模拟退火等启发式方法。

这套方法论也不只属于快递：编译器在指令调度时用类似思想枚举寄存器分配顺序，EDA 工具在芯片布线时求解引脚连接顺序，调度系统在安排多任务执行序列时同样借助它。状态压缩 DP 教会小明的，其实是一句普适的话——当状态空间大到爆炸时，试着找出“真正需要记住的信息”，其余统统扔掉。

T(n)=O(n2⋅2n),S(n)=O(n⋅2n)\displaystyle T(n) = O(n^2 \cdot 2^n), \quad S(n) = O(n \cdot 2^n)
  1. 状态总量mask 有 2^n 种取值，乘以终点 i 的 n 个可能，得到 n·2^n 个状态。
    n×2n\displaystyle n \times 2^n
  2. 每状态转移数对固定 (mask, i)，最多枚举 n 个 j，每个转移 O(1)。
    O(n)\displaystyle O(n)
  3. 总时间状态数 × 每状态转移数 = O(n · 2^n) × O(n)。
    O(n2⋅2n)\displaystyle O(n^2 \cdot 2^n)

AI 应用场景

场景1：物流配送路径优化

阶段：决策优化 / 路径规划

解决的问题：人工排线依赖老师傅经验，配送点超过10个就难以凭直觉找到最优顺序；AI将配送点建模为TSP，用状压DP在小规模（≤20个点）下求出精确最优路线，并作为大规模启发式算法的评估基准。

具体案例：某社区团购站点每天有15个配送点，接入状压DP求解后，单车日均行驶里程缩短了12%，同时把排线时间从人工的40分钟压缩到1秒以内。

场景2：PCB钻孔与芯片引脚布线

阶段：搜索优化

解决的问题：电路板上有大量孔位需要钻孔机依次加工，钻头移动距离直接决定工时；芯片引脚间的连线顺序同样影响布线面积与信号时延。两者都能抽象为“访问一批点并回到原点”的TSP。

具体案例：某PCB制造厂将钻孔坐标转换为距离矩阵，用状压DP计算最优钻孔顺序，单块板加工时间下降18%；FPGA布局布线工具中也用类似思路优化引脚连接。

场景3：多任务执行顺序规划

阶段：调度决策

解决的问题：机器人执行多个工位任务时，换线时间随顺序不同而变化；编译器对中间代码进行指令调度时，也要在资源约束下寻找最优执行序列。这些“顺序决定成本”的问题都可以套用TSP的建模框架。

具体案例：某自动化产线的机械臂需要在6个工位间完成点焊，将工位坐标转化为距离矩阵后，状压DP给出最优路径，单循环节拍从52秒缩短到41秒。

Python 演示

python62 行
import math  def solve_tsp(dist):    """返回(最短回路长度, 最优路径列表)，从城市0出发并回到0。"""    n = len(dist)    size = 1 << n    dp = [[float("inf")] * n for _ in range(size)]    parent = [[-1] * n for _ in range(size)]    dp[1][0] = 0  # 只访问了城市0，停在0     for mask in range(size):        for i in range(n):            if not (mask >> i) & 1:  # 城市i不在集合中                continue            if dp[mask][i] == float("inf"):                continue            for j in range(n):                if (mask >> j) & 1:  # j已访问，跳过                    continue                nmask = mask | (1 << j)                nd = dp[mask][i] + dist[i][j]                if nd < dp[nmask][j]:                    dp[nmask][j] = nd                    parent[nmask][j] = i  # 记录前驱     full = size - 1    best = float("inf")    last = -1    for i in range(1, n):        val = dp[full][i] + dist[i][0]  # 最后从i回到0        if val < best:            best = val            last = i     path = []    mask = full    cur = last    while cur != -1:  # 倒推还原路径        path.append(cur)        nxt = parent[mask][cur]        mask ^= 1 << cur        cur = nxt    path.reverse()    path.append(0)  # 补上回到起点的闭环    return best, path  def main():    pts = [(0, 0), (3, 4), (6, 1), (2, 7), (5, 5)]    n = len(pts)    dist = [[0] * n for _ in range(n)]    for i in range(n):        for j in range(n):            dist[i][j] = math.hypot(pts[i][0] - pts[j][0], pts[i][1] - pts[j][1])    best, path = solve_tsp(dist)    print("best dist:", round(best, 2))    print("best path:", " -> ".join(str(c) for c in path))  if __name__ == "__main__":    main()
目的：完整实现TSP的状压DP求解，包含状态转移、前驱记录与路径回溯，输出最短回路长度与具体访问顺序。
  1. dp = [[float("inf")] * n for _ in range(size)]初始化一张大小为 2^n × n 的账本，所有格子先设为“无穷大”，表示尚未到达。
  2. dp[1][0] = 0起点状态：只点亮城市0的灯，站在城市0，里程为0。
  3. if not (mask >> i) & 1查灯：第 i 位是0说明城市 i 还没访问，跳过这个非法的“当前位置”。
  4. nmask = mask | (1 << j)开灯：把城市 j 的灯点亮，得到新集合。
  5. if nd < dp[nmask][j]只保留更短的路程，保证每个格子存的都是最小值。
  6. parent[nmask][j] = i记下“谁把我带到了这个状态”，供回溯使用。
  7. val = dp[full][i] + dist[i][0]所有灯亮后，从最后一站 i 回站点的总里程。
  8. mask ^= 1 << cur关灯：倒推时把当前城市的灯熄灭，回到上一状态。

常见误区

误区“集合状态压缩后，dp[mask] 就能表示当前集合的最优值了，为什么还要加一个 i？我不关心最后停在哪，直接取 min 不行吗？”

正解如果把终点 i 丢掉，转移时就不知道“从哪个城市出发去扩展下一个城市”，无法计算 dist[j][i]。就像小明送货，账本只记“这几家送完了”却不记“车停哪”，下一站从哪开过去就无从谈起。所以必须用二维 dp[mask][i]：第一维管“去过哪”，第二维管“现在在哪”，二者缺一不可。

为何常见：因为初学者熟悉一维线性DP，看到“状态压缩”后第一反应是“集合本身就是一个维度”，容易忽视TSP中“当前位置”这个必要的额外维度。

误区“既然要从城市0出发，那 dp[0][0] = 0 才对，表示一个城市都没访问。”看起来很有道理，但状态含义对不上了。

正解dp[0][0] 表示“空集且站在城市0”，这在物理上不成立——你没访问过0，怎么会站在0？正确写法是 dp[1][0] = 0，即“集合里已经包含城市0（起点灯亮），且停在0”。类比小明：出发那一刻，站点的灯就该是亮的，因为“城市0”已经“被访问”了。

为何常见：很多教材在简化模型时会用 dp[0][0]=0 配合“先造城市0再出发”的写法，初学者记混了不同约定，导致状态链条断裂。

误区“判断城市 i 是否已访问，用 mask & (1 << i) 不就行了？为什么还要 (mask >> i) & 1？两个差不多吧。”或者反过来，把开灯写成 mask ^ (1 << i)。

正解查灯的标准写法是 (mask >> i) & 1，结果是0或1；mask & (1 << i) 的结果是 2^i 或 0，也能用来判断但容易在后续算术运算中埋雷。开灯一定要用按位或 mask | (1 << i)，而 mask ^ (1 << i) 是“拨动开关”——灯亮变灭、灯灭变亮，用在开灯语义上时会翻车。就像小明拨灯：开灯要用“点亮”按钮，不能用“切换”按钮，否则亮着的灯会被关掉。

为何常见：按位与、或、异或在最底层长得太像，初学者靠“背口诀”而不是靠语义理解，一紧张就用错。

误区“我从 (mask, i) 出发，下一步去 j，所以应该写 dp[mask | (1 << j)][j] = min(dp[mask][i] + dist[i][j])，这不是一样的吗？怎么我写出来答案不对？”

正解递推式本身没有错，错的是遍历顺序。如果你用“拉”式（从 mask 去掉 i 转移过来），必须保证 mask 从小到大遍历，因为去掉一个 1 后 mask 一定更小，小状态先算好。如果你用“推”式（从 mask 扩展到 mask|(1<<j)），也要从小到大遍历，并且要处理“当前状态不可达就跳过”的边界。两种写法等价，但混用公式和循环顺序就会得到错误结果。

为何常见：教材里有时写拉式、有时写推式，初学者对着公式抄代码时没注意配套的循环方向和初始化，张冠李戴。

误区“20个城市，20! 虽然大，但计算机不是很快吗？我优化一下照样能跑完吧？直接枚举排列加剪枝不就行了？”

正解20! ≈ 2.4×10^{18}，哪怕每纳秒算一条路线，也要 77 年；而状压 DP 只要 20² × 2^{20} ≈ 4.2×10^8 次运算，普通电脑一秒内完成。差距是十亿倍，不是优化个常数因子能追上的。这就是“算法设计”和“程序调优”的本质区别——换一个数量级的思路，远比把循环写快几倍重要。

为何常见：人对指数增长缺乏直觉，20 的阶乘听起来只是“20个数相乘”，实际增长曲线远超想象；只有亲手跑一遍对比才能建立体感。

面试题

Q1. 在TSP的状压DP中，二进制掩码 mask 的每一位表示什么？

单选题 · easy

  • A.对应城市是否已访问← 正确答案
  • B.两个城市之间的距离
  • C.当前路径的总长度
  • D.DP数组的层数编号

答案：A。mask 的每一位对应一个城市，1 表示该城市已访问（灯亮），0 表示未访问，这与“开关灯面板”的语义一致。距离和长度是 dp 表里存的值，不是 mask 的含义。

Q2. n 个城市的TSP，朴素枚举所有可能路线的复杂度量级是？

单选题 · easy

  • A.O(n)
  • B.O(n log n)
  • C.O(n!)← 正确答案
  • D.O(2^n)

答案：C。枚举所有排列需要计算 n×(n-1)×……×1 = n! 种顺序，因此复杂度是阶乘级。2^n 是“集合状态”的数量，而不是完整路线的数量，容易混淆。

Q3. 检查 mask 中城市 i 是否已访问，正确的位运算表达式是？

单选题 · easy

  • A.mask | (1 << i)
  • B.mask ^ (1 << i)
  • C.(mask >> i) & 1← 正确答案
  • D.mask & ~(1 << i)

答案：C。把第 i 位移到最低位再与 1 相与，结果为 1 表示灯亮、0 表示灯灭。A 是开灯（置1），B 是拨动开关（翻转），D 是关灯（置0），都不是“读灯”操作。

Q4. 已知 dp[mask][i] 表示已访问集合为 mask、当前停在城市 i 的最短里程，下面哪个是“拉”式转移方程的正确形式？

单选题 · mid

  • A.dp[mask][i] = min(dp[mask^(1<<i)][j] + dist[j][i])← 正确答案
  • B.dp[mask][i] = min(dp[mask][j] + dist[j][i])
  • C.dp[mask][i] = min(dp[mask|(1<<i)][j] + dist[i][j])
  • D.dp[mask][i] = dp[mask^(1<<i)][i] + dist[i][j]

答案：A。先退一步：把城市 i 从集合中摘掉（mask ^ (1<<i)），枚举上一站 j，加上 j 到 i 的距离，取最小。B 没有去掉 i，集合自相矛盾；C 是推式的方向；D 的 j 被错误替换成 i。

Q5. 从城市0出发访问所有城市并回到0，dp[1][0] 应初始化为多少？

单选题 · mid

  • A.0← 正确答案
  • B.1
  • C.∞
  • D.dist[0][0]

答案：A。dp[1][0] 表示“已访问集合只有城市0，且停在城市0”，还没走任何路，里程自然是0。设为∞会导致起点不可达，整张表全部失效。

Q6. 关于位运算 1 << i，下列说法正确的有？

多选题 · mid

  • A.结果是 2 的 i 次幂← 正确答案
  • B.配合按位或可将 mask 的第 i 位置为 1← 正确答案
  • C.它的优先级高于所有运算符
  • D.1 << n 等于 2^n，可作为 DP 数组的总行数← 正确答案

答案：ABD。左移 i 位就是乘以 2^i；mask | (1<<i) 用来“开灯”；DP 数组行数为 2^n = 1<<n。左移优先级低于加减、高于比较，不是“高于所有运算符”，C 错。

Q7. 当 n=20 时，状压DP的时间复杂度是？

单选题 · mid

  • A.O(20!)
  • B.O(20 × 2^20)
  • C.O(400 × 2^20)← 正确答案
  • D.O(20^2)

答案：C。状态数 n·2^n，每个状态枚举 n 个转移，总复杂度 O(n²·2^n)，代入 n=20 即 400×2^20。B 少乘了一个 n，D 漏掉了指数项。

Q8. 关于TSP路径回溯的正确做法，下列说法正确的是？

多选题 · hard

  • A.用 parent[mask][i] 记录最优路线中城市 i 的前一站← 正确答案
  • B.从全亮状态 (1<<n)-1 和最优终点 i 开始倒推← 正确答案
  • C.直接依据 dist 矩阵就可以重建完整路径
  • D.每倒推一步，用 mask ^= (1<<cur) 把当前城市从集合中移除← 正确答案

答案：ABD。回溯必须依赖转移时记录的决策点，dist 矩阵只含距离、不含“谁先谁后”，无法重建路径。倒推时从终点沿 parent 链前进，同时熄灭当前城市的灯，直到回到起点。

Q9. 状压DP相比暴力枚举，核心优化在于？

单选题 · hard

  • A.用邻接矩阵替代邻接表存储图
  • B.用集合状态合并大量“终点相同的重复路线”，避免重复计算← 正确答案
  • C.每次贪心选择距离最近的城市
  • D.用分支限界法剪掉不可能的分支

答案：B。暴力枚举把每条完整路线都算一遍；状压DP把“访问集合相同、终点相同”的所有路线合并成一个状态，只存最优值。这正是动态规划“重叠子问题”思想的体现，也是 n! 降到 n·2^n 的本质原因。

Q10. 关于枚举 mask 的所有子集 sub = (sub-1) & mask，下列说法正确的有？

单选题 · multiple

  • A.会遍历包含空集在内的全部子集
  • B.每次减1后与mask求交，自动跳过不在mask中的位← 正确答案
  • C.子集的遍历顺序是从小到大
  • D.总迭代次数等于 mask 的子集个数 2^{popcount(mask)}← 正确答案

答案：BD。该技巧从 mask 本身开始，不断 (sub-1) & mask，跳过无用位，迭代次数恰好是子集数 2^k（k为mask中1的个数）。遍历顺序是从大到小，且通常循环到 sub=0 就结束、不包含空集（空集需单独处理），因此 A、C 错误。