清晨六点，快递员小陈看着手机备忘录里密密麻麻的客户名单，深吸一口气。今天有 6 家客户要送货，每一家送完，他就在名字后面划一道勾。这张“划掉 / 没划掉”的清单，就是他一天工作的灵魂——而他不知道的是，这张清单在计算机科学里有个响亮的名字：位掩码（bitmask）。 更让小陈头疼的是路线问题：6 家客户分散在城市的各个角落，怎么安排顺序，才能让总里程最短？这就是著名的旅行商问题（TSP）。如果挨个尝试所有顺序，6 家就是 720 种，10 家就是 362 万种，20 家更是天文数字——普通计算机算到宇宙毁灭也跑不完。但借助“打卡清单”的思路，计算机可以聪明地记住每一种“已经送过哪几家、现在在哪一家”的状态，像滚雪球一样一层层推出最优路线。这种把“集合状态”编码成二进制数字、再拿来做动态规划的技巧，就是状态压缩 DP。

岗位关联

状态压缩 DP 是算法面试与工程优化中的高频核心技能，掌握它，你就能优雅地解决旅行商、棋盘覆盖等“小规模集合”的组合爆炸问题，这也是通往高级算法工程师的必经之路。

目录
  1. 可视化演示
  2. 位掩码：一张会算数的打卡清单
  3. 位运算：清单上的四种神操作
  4. TSP 建模：最优路线的转移方程
  5. 子集枚举：摊开所有组合
  6. 空间优化：两张纸的账本
  7. 应用场景：一个法子走天下
  8. AI 应用场景
  9. Python 演示
  10. 常见误区
  11. 面试题

可视化演示

展示状态压缩DP核心机制：位掩码表示集合状态（二进制位映射元素+位运算增删查）、TSP旅行商状压DP解法（dp[mask][i]状态转移+城市路径）、子集枚举trick(sub=(sub-1)&mask)+空间优化（滚动数组），交互切换核心维度。

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

位掩码表示集合状态 n个元素子集用0~2^n-1整数表示，二进制位映射元素存在性 添加mask|1 Brian Kernighan法统计集合大小，dp[mask]一维数组 mask = sum(bit_i * 2^i), dp[mask] compresses set state 位掩码+位运算+状态压缩

位掩码：一张会算数的打卡清单

小陈的送货清单上，每一家客户对应一行。送完一家，他就在名字上划一道勾。这个“划了 / 没划”的二维状态，如果翻译成计算机的语言，就是二进制里的 1 / 0——一家客户占用一个“位”。把 6 家客户的勾选状态横向排成一排，就得到一个 6 位的二进制数，比如 101100 就表示“第 0、2、3 家已送，其余没送”。这个二进制数，就是位掩码。

位掩码的精髓在于：一个普普通通的整数，就能完整描述一个集合。比如十进制数 5，写成二进制是 101，它同时就代表着集合 {0, 2}（从右往左第 0 位和第 2 位是 1）。反过来，任何一个集合也能翻译成一个整数。这种“集合 ⟷ 整数”的互相映射，是状态压缩 DP 的地基。你不需要再开一个布尔数组去记录“谁来过”，一个 int 变量就全搞定了。

不过这份“清单”也有个天然限制：一个 int 只有 32 位，就算用 64 位整数，也只能表示约 60 个元素的集合。所以在实际做题和工程中，状态压缩 DP 通常只用于 n ≤ 20 的场景——因为内存开销也是以 2 的 n 次方增长的，稍后会详细算这笔账。

小陈盯着清单突然明白：他根本不用拿笔一格格划，只要记住一个数字，比如“今天已完成 37（二进制 100101）”，就能知道第 0、2、5 家已经送完。这张“会算数的清单”，让整个送货状态变成了一枚可以随身携带的“数字印记”。

集合S⟷mask=∑i∈S2i\displaystyle 集合S \longleftrightarrow mask = \sum_{i \in S} 2^{i}
这个公式说明：集合中的每个元素 i，对应二进制中的第 i 位；把集合里所有元素对应的 2 的幂加起来，就得到了唯一的整数 mask。
  1. 集合映射到整数把集合 S 中的每个元素 i 看作一个“开关”，开关在二进制第 i 位。打开（=1）表示元素在集合中，关闭（=0）表示不在。
    mask=∑i∈S2i\displaystyle mask = \sum_{i \in S} 2^{i}
  2. 二进制位权重第 i 位的权重是 2 的 i 次方。从右往左数，第 0 位权重是 1，第 1 位是 2，第 2 位是 4……这正是普通二进制数。
    2i\displaystyle 2^{i}
  3. 反向读出集合给定 mask，检查第 k 位是否为 1，就能判断元素 k 是否在集合中。这段“读清单”的功夫，下节讲位运算时展开。
    mask  &  (1<<k)≠0\displaystyle mask \;\&\; (1 << k) \neq 0

位运算：清单上的四种神操作

有了清单，小陈每天要做很多动作：查看某家送没送、把某家划掉、突然发现某家要退回重送、清点今天一共送了几家。这些动作，对应到位掩码上就是一组“位运算”。它们是状态压缩 DP 的手脚，没有它们，光有清单也寸步难行。

最常用的四个动作：测试某一位是不是 1（这家送了吗）、置位把某一位改成 1（这家刚送完，打勾）、清除把某一位变成 0（这家要重送，取消勾）、以及 lowbit 把二进制里最低位的那个 1 单独抠出来（找到“最近一次送货”的位置）。这些操作全部是 O(1) 的，比遍历数组快得多——因为 CPU 对整数的位运算是一瞬间完成的。

位运算符包括按位与 &、按位或 |、按位异或 ^ 和取反 ~。它们和逻辑运算 and / or 最大的不同是：逻辑运算只产生 True/False，而位运算是逐位地对二进制每一位做操作，结果仍然是一个整数。这个区别至关重要——状态转移靠的正是“整数与整数的逐位加工”。

小陈把这四个动作练得滚瓜烂熟：查看清单、划勾、改勾、找最近一笔。有了这套“手指功夫”，他操作清单的速度肉眼可见地快了起来——而接下来，他要面对真正的难题：路线规划。

(mask>>k)&1;mask ∣ (1<<k);mask&∼(1<<k);lowbit(x)=x&(−x)\displaystyle (mask >> k) \& 1; \qquad mask \,|\, (1 << k); \qquad mask \& \sim(1 << k); \qquad lowbit(x) = x \& (-x)
这四式分别是“测试第 k 位是否为 1”“把第 k 位置 1”“把第 k 位清 0”“取出最低位的 1”。它们构成了位掩码操作的基本工具箱。
  1. 测试第 k 位先把 mask 右移 k 位，让第 k 位跑到最低位，再和 1 做与运算。结果是 1 说明该位是 1，否则是 0。
    (mask>>k)&1\displaystyle (mask >> k) \& 1
  2. 置位（打勾）用 1 << k 构造一个“只有第 k 位是 1”的数，再和 mask 做按位或。因为 1 OR 任何数都是 1，所以第 k 位必变 1，其他位不受影响。
    mask ∣ (1<<k)\displaystyle mask \,|\, (1 << k)
  3. 清除（取消勾）~(1 << k) 得到“只有第 k 位是 0”的数，再与 mask 做按位与。因为 0 AND 任何数都是 0，所以第 k 位被强制清零。
    mask&∼(1<<k)\displaystyle mask \& \sim(1 << k)
  4. lowbit 取最低位 1负数在计算机里是补码表示，x & (-x) 能精准地只留下最低位的那个 1。例如 x=12（1100），结果就是 4（0100）。
    x&(−x)\displaystyle x \& (-x)

TSP 建模：最优路线的转移方程

现在到了小陈一天中最头疼的环节：怎么安排路线最省油？ 这就是旅行商问题：给定 n 座城市和两两之间的距离，找一条从起点出发、恰好访问每座城市一次、最后回到起点的最短环路。

朴素的想法是枚举所有排列。3 座城市 6 种，5 座城市 120 种，10 座城市就是 3628800 种——这叫阶乘爆炸。而状态压缩 DP 的妙处在于：把“已经访问过哪些城市”压缩成 mask，“当前停在哪个城市”单独作为一维，于是状态总数为 2^n × n，比 n! 小了好几个数量级。

定义 dp[mask][i]：已经访问过 mask 中所有城市、并且当前正站在城市 i，此时走过的最短距离。转移时，我们思考“最后一步”：在到达 i 之前，人一定在某座城市 j，且 j 也在 mask 中；把“已经访问过除了 i 之外的所有城市、停在 j”的状态，加上 j 到 i 的距离，就是一条候选路线。对所有的 j 取最小值，就得到了 dp[mask][i]。

小陈在纸上推演：要算出“今天 5 家全送完、最后停在 3 号客户”的最短里程，只需要看“前 4 家送完、最后停在 0/1/2/4 号”的四种情况，再分别加上对应的那一段路，取最小。这样一层层往回推，最终 dp[全1][i] + w[i][0] 里最小的那个，就是整个环路的最优解。他把这个“倒着拆、正着填”的思路叫做“砍尾巴大法”——每算一步，就砍掉路径的最后一小截。

dp[mask][i]=min⁡j∈maskj≠i{dp[mask⊕(1<<i)][j]+w[j][i]}\displaystyle dp[mask][i] = \min_{\substack{j \in mask \\ j \ne i}} \left\{ dp[mask \oplus (1 << i)][j] + w[j][i] \right\}
这个转移方程是 TSP 的核心：把“访问完 mask 且最后停在 i”这个大问题，拆成“访问完 mask 去掉 i、最后停在 j”的小问题，再拼接上 j→i 这一小段路。
  1. 状态含义dp[mask][i] 表示已经送完 mask 中的客户、快递员此刻站在客户 i 门口时，走过的最短里程。
    dp[mask][i]\displaystyle dp[mask][i]
  2. 去掉 i 的前驱状态mask ⊕ (1 << i) 表示从 mask 中把第 i 位翻转为 0，也就是“还未访问 i 时的集合”。
    mask⊕(1<<i)\displaystyle mask \oplus (1 << i)
  3. 枚举上一站 j上一站 j 必须属于“去掉 i 后的集合”，而且 j 不能等于 i 自己。
    j∈mask,  j≠i\displaystyle j \in mask, \; j \ne i
  4. 拼接与取最值前驱状态的最短里程，加上客户 j 到客户 i 的这段路，就形成一条完整候选；对所有 j 取最小，得到本状态的最优值。
    min⁡j{dp[mask⊕(1<<i)][j]+w[j][i]}\displaystyle \min_{j} \left\{ dp[mask \oplus (1 << i)][j] + w[j][i] \right\}

子集枚举：摊开所有组合

在填表的过程中，小陈还发现一个隐藏的技巧：有时候他需要枚举“某个集合的所有子集”。比如设计多日送货方案时，要知道“从 5 个客户中任意挑出 2 个”共有多少种选法、每种方案的总距离是多少。直接枚举组合可以用递归，但位运算给了一个一行代码的写法。

设当前要枚举的“大集合”是 mask，我们要依次访问它的所有非空子集。核心递推式是：sub = (sub - 1) & mask。它的原理很巧妙：sub 减 1 会让最低位的 1 变成 0、更低位全变 1；再与 mask 按位与，就把“mask 中原本没有的位”全部过滤掉。于是 sub 会从 mask 本身开始，依次跳过所有不属于 mask 的位，精确地遍历 mask 的每一个子集，直到变成 0。

这个技巧的复杂度也是经典的：对所有 mask 枚举其所有子集，总复杂度是 O(3^n)。因为每个元素有三种状态：只在 mask 中、只在 sub 中、在两者中。相比 O(2^n) 的普通 DP，它多了一个维度，但也因此能处理“子集内部还需再分类”的更复杂问题。

小陈把这条式子写在小本本上，每次要“摊开所有组合”时，就用它一行行列出所有子集。原本要写十几行递归的活，现在一个 for 循环就解决了，他不禁感叹：位运算真是算法世界里最锋利的瑞士军刀。

subnext=(sub−1)  &  mask\displaystyle sub_{next} = (sub - 1) \;\&\; mask
这行代码是枚举子集的核心：每循环一次，sub 就自动跳到下一个子集，且保证不重不漏。
  1. 减一操作sub 减 1 后，最低位的 1 变成 0，它右边的所有 0 全部变成 1。这是为了让“指针”跳到下一个更小的数。
    sub−1\displaystyle sub - 1
  2. 与 mask 求交& mask 把结果中不属于 mask 的位全部清掉，确保 sub 始终是 mask 的子集。
    (sub−1)&mask\displaystyle (sub - 1) \& mask
  3. 循环终止当 sub 减到 0 时，(0 - 1) & mask 会得到 mask 本身，因此循环必须判断 sub > 0，并在循环体外单独处理空集。
    sub>0\displaystyle sub > 0

空间优化：两张纸的账本

随着客户越来越多，小陈发现自己的“备忘录”越来越厚。状态总数为 2^n × n，当 n=20 时，就是 100 多万 × 20 ≈ 2000 万个数字，每个数字占 8 字节，约占 160MB 内存——这已经逼近普通程序的极限。于是他开始思考：能不能省点纸？

滚动数组的思路来自一个朴素观察：很多 DP 的状态转移，只依赖“相邻层”的数据。如果第 k 层的计算只需要第 k-1 层的值，那么第 k-2 层及更早的层就可以丢掉，只需维护两个数组来回滚动。这样内存能从 O(2^n × n) 降到 O(2^n)。在经典的背包问题、部分棋盘覆盖问题中，这种优化非常有效。

但小陈很快发现：不是所有问题都能滚动。TSP 的转移中，dp[mask][i] 要从 dp[mask 去掉一位][j] 转移过来，mask 的二进制值 20（10100）可能依赖 16（10000）和 4（00100），它们之间并没有“大小相邻一层”的规律——mask 维度上每个状态都可能被任何其他状态依赖。因此 TSP 的 mask 维度不能滚动，只能老老实实开满。这是空间优化中最容易踩的坑：先判断依赖方向是否规整，再决定是否滚动。

小陈最终决定：TSP 老老实实开大数组，但换用更紧凑的数据类型（比如只需要存距离，用 4 字节 int 而非 8 字节 double），把内存压到 80MB。他悟出一个道理：优化不是盲目套模板，而是先看清依赖关系这张“账本”的脉络。

内存优化:  O(2n×n)  →  O(2n)(仅当转移仅依赖相邻层)\displaystyle 内存优化: \; O(2^n \times n) \;\rightarrow\; O(2^n) \quad (\text{仅当转移仅依赖相邻层})
滚动数组能把内存缩小 n 倍，但前提是状态转移的依赖关系“层层推进、只碰邻层”。TSP 的 mask 转移是网状依赖，不满足这个前提。
  1. 原始内存2^n 种集合 × n 个“当前城市”，所以总状态数约 2^n × n。
    States=2n×n\displaystyle States = 2^n \times n
  2. 滚动压缩如果转移只依赖“上一轮”的数据，就只保留两个轮次的数组，内存变成约 2^n。
    2n×n  →  2n\displaystyle 2^n \times n \;\rightarrow\; 2^n
  3. 依赖判断压缩前必须检查转移方程中的 mask 关系——如果 mask 可能依赖任意更小的 mask'，而不只是 mask-1，就不能滚动。
    dp[mask][i]←dp[mask′][j],mask′=mask⊕(1<<i)\displaystyle dp[mask][i] \leftarrow dp[mask'][j], \quad mask' = mask \oplus (1<<i)

应用场景：一个法子走天下

从 TSP 出发，小陈发现“打卡清单”这套思路几乎是个万能钥匙，稍加变形就能解锁一大片问题。第一个是棋盘覆盖：要在 m×n 的棋盘上铺某种形状的骨牌，问有多少种铺法。可以把“当前行哪些格子已经被占用”压缩成 mask，逐行转移，状态只需要一行——这是状态压缩 DP 最经典的入门题。

第二个是排列计数：比如“n 个人排队，某些人不能相邻，问有多少种合法排列”。把“哪些人已经排好”存成 mask，dp[mask][i] 表示“已排好 mask 中的人、队尾是 i”的方案数，转移时检查 i 能否接在 j 后面。这与 TSP 的转移结构惊人地相似。

第三个是最短哈密顿路径：和 TSP 只差一个“不用回到起点”。状态定义和转移方程完全一样，只在最终答案处不同——TSP 要求 dp[full][i] + dist[i][0] 的最小值，而哈密顿路径直接取 dp[full][i] 的最小值即可。这也说明了 TSP 与路径问题的本质联系：多一条回程边而已。

小陈的笔记本上，TSP、棋盘覆盖、排列计数、哈密顿路径被画在同一个思维导图里，中心写着四个大字：“集合压缩”。他这才发现，自己从一张送货清单出发，居然摸到了一整类算法的命脉。所谓状态压缩 DP，不过是用一个整数装下整个集合，再用聪明的转移代替盲目的穷举——暴力枚举的尽头，就是动态规划的起点。

---

TSP答案=min⁡i{dp[full][i]+w[i][0]};路径答案=min⁡i{dp[full][i]}\displaystyle \text{TSP答案} = \min_{i} \left\{ dp[full][i] + w[i][0] \right\}; \qquad \text{路径答案} = \min_{i} \left\{ dp[full][i] \right\}
两行答案之差，就是“闭环”与“开链”之别。理解这个对比，就理解了 TSP 的本质结构。
  1. 全访问状态full = (1 << n) - 1，二进制全为 1，表示所有城市都已经访问完。
    full=(1<<n)−1\displaystyle full = (1 << n) - 1
  2. TSP 闭环绕回最后停在 i 后，还要走 w[i][0] 回到起点 0，所以答案要加回程边。
    min⁡i{dp[full][i]+w[i][0]}\displaystyle \min_{i} \{ dp[full][i] + w[i][0] \}
  3. 哈密顿开链只需要“访问全部城市”而不要求回到起点，所以直接取 dp[full][i] 的最小值即可。
    min⁡i{dp[full][i]}\displaystyle \min_{i} \{ dp[full][i] \}

AI 应用场景

物流配送路径规划

阶段：决策优化

解决的问题：传统物流调度员凭经验排线，城市一多就顾此失彼，路线重复率高、油耗大。AI 用状态压缩 DP 对 20 个以内的配送点做精确最优排线，作为大规模车辆路径问题（VRP）的子模块，给出“理论上最短”的参考路线，再用启发式算法扩展到上百个点。

具体案例：某同城生鲜平台每天要为 30 个前置仓计算配送路线。AI 系统先按区域把客户切分成小组（每组 ≤ 18 个点），组内用状态压缩 DP 求精确最短路径，组间用遗传算法衔接。上线后单车日均行驶里程下降 12%，准时率提升到 99%。

数控机床钻孔路径优化

阶段：工艺参数优化

解决的问题：PCB 电路板上有成千上万个孔要钻，钻头从一块板移动到下一块板，移动路径直接决定加工时间。传统 CAM 软件按行列顺序钻孔，路径冗余严重。AI 将每个钻孔位置视为一座“城市”，用 TSP 的状态压缩 DP 求出最优钻孔顺序（在孔数较少的小板场景），大幅缩短空行程。

具体案例：一家 PCB 代工厂的多层板有约 15 个定位孔，原本钻孔顺序由工程师手工指定，单板耗时 4.2 秒。改用 TSP 优化后，钻头空行程减少 38%，单板耗时降至 2.9 秒，产线节拍显著加快。

通信基站巡检路线编排

阶段：运维调度

解决的问题：巡检员每天要跑多个基站，每个基站都有服务窗口时间（比如只能上午维护），这比标准 TSP 多了一层时间窗约束。AI 用状态压缩 DP 记录“已巡检集合 + 当前基站”，并在转移时校验时间窗可行性，输出一条满足所有窗口的最短巡检路线。

具体案例：某电信运营商地市分公司有 12 个核心基站在同一天需要巡检。使用状态压缩 DP 排线后，巡检总里程从 235km 降到 168km，且所有基站均在窗口内完成，运维成本每月节省约 8000 元。

Python 演示

python30 行
def solve_tsp(dist):    n = len(dist)    total = 1 << n    dp = [[float('inf')] * n for _ in range(total)]    dp[1][0] = 0     for mask in range(1, total):        for i in range(n):            if dp[mask][i] == float('inf'):                continue            for j in range(n):                if (mask >> j) & 1:                    continue                nxt = mask | (1 << j)                cost = dp[mask][i] + dist[i][j]                if cost < dp[nxt][j]:                    dp[nxt][j] = cost     full = total - 1    return min(dp[full][i] + dist[i][0] for i in range(1, n))  if __name__ == '__main__':    dist = [        [0, 10, 15, 20],        [10, 0, 35, 25],        [15, 35, 0, 30],        [20, 25, 30, 0],    ]    print(solve_tsp(dist))
目的：用状态压缩 DP 精确求解 4 座城市的 TSP，输出最短闭环距离。
  1. dp = [[float('inf')] * n for _ in range(total)]开一张 2^n 行、n 列的“账本”，所有格子先填无穷大。
  2. dp[1][0] = 0初始状态：只访问过城市 0、当前站在 0，距离为 0。
  3. for mask in range(1, total)按集合从小到大推进，保证每个 mask 依赖的小集合都已算好。
  4. if (mask >> j) & 1: continue测试第 j 位：若 j 已在集合中则跳过，避免重复访问。
  5. nxt = mask | (1 << j)置位操作：把 j 加入集合，得到新状态。
  6. full = total - 1全 1 的 mask，表示所有城市都已访问。
  7. min(dp[full][i] + dist[i][0] for i in range(1, n))枚举最后停留的城市 i，加上回起点 0 的路程，取最小。

常见误区

误区总觉得位掩码是高深莫测的黑科技，好像必须要背很多玄妙的公式才能用。看到 `mask ^ (1 << i)` 就头大，觉得这是只有竞赛大佬才懂的东西。

正解位掩码的本质就是一个普通整数，二进制位不过是“开关”。就像快递员的打卡清单，划勾就是 1、没划就是 0。你完全可以把 mask 读作“已访问集合的编号”，把 mask | (1<<j) 读作“把 j 加进集合”。一旦用集合思维替代位运算思维，一切都顺了。

为何常见：教材往往直接甩出位运算表达式，缺乏“一个整数代表一个集合”的直觉铺垫，导致读者被符号吓退。

误区`mask & (1 << k)` 是不是在问“mask 和 1<<k 同时为真吗”？既然都是判断真假，那 `&&` 和 `&` 应该差不多吧？新手经常把逐位运算和逻辑运算混为一谈。

正解逻辑运算 and / or 返回的是布尔值 True/False；位运算 & / | 是逐位加工两个整数，返回的是一个新的整数。比如 5 & 3 = 1，因为 101 和 011 逐位与得到 001。在 TSP 转移里，mask | (1<<j) 是在“数字层面”把第 j 位翻成 1，而不是在“真假层面”做判断。

为何常见：中文里都叫“与/或”，且语法上 & 和 && 长得像，新手极容易混淆两类运算的语义和结果类型。

误区直接写一个双层循环：外层枚举“当前在哪座城市 i”，内层枚举“访问集合 mask”，结果算出来的答案经常偏大或报错。

正解TSP 转移中，dp[mask][i] 依赖 dp[mask 去掉 i][j]——去掉了 i 的 mask 一定比原 mask 的二进制值更小吗？不一定！比如 mask=20（10100）去掉 4 位后是 16（10000），去掉 2 位后是 4（00100）。所以必须外层从小到大枚举 mask，保证所有更小集合先算完，再算更大集合。

为何常见：惯性思维把“当前城市”当成主循环变量，却忽视了集合维度才是转移的“时间轴”。

误区滚动数组能省内存，那 TSP 也滚动一下，把 2^n × n 压成 2^n，岂不美哉？

正解滚动数组只适用于“转移仅依赖相邻层”的问题（如背包）。TSP 的 dp[mask][i] 可能依赖任意更小的集合，甚至 mask 值跳来跳去，不存在“一层一层”的规整关系。强行滚动会丢失状态，算出错误答案。压缩前必须画出依赖图，看清状态之间的引用方向。

为何常见：滚动数组是 DP 优化中的“明星技巧”，新手容易盲目套用，忽略了依赖结构才是决定能否滚动的关键。

误区枚举子集的代码不就一个 for 循环吗？外层 2^n、内层每次 O(1)，所以总复杂度也是 O(2^n)。

正解注意内层循环的次数不是常数，而是随 mask 变化的。对每个 mask，内层要枚举它的所有子集，而总共有 3^n 个“元素→状态”的二元关系（每个元素有三种归属）。所以总复杂度是 O(3^n)，n=15 时约 1400 万，n=20 时约 34 亿，差距巨大。设计算法前必须先算清这笔账。

为何常见：只数了外层循环的规模，忽略了内层循环次数随 mask 动态变化，导致复杂度估算严重偏低。

面试题

Q1. 判断整数 mask 的第 k 位是否为 1，正确写法是？

单选题 · easy

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

答案：B。把 mask 右移 k 位，让第 k 位落到最低位，再与 1 做按位与，结果为 1 则第 k 位为 1。A 是按位与了错误的位，C 是置位操作，D 是翻转操作。就像快递员想查“3 号客户送没送”，得先翻到清单第 3 行再看勾，而不是直接问整张清单。

Q2. 想将 mask 的第 k 位设为 1（不影响其他位），应使用？

单选题 · easy

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

答案：C。1 << k 构造出“只有第 k 位是 1”的数，与 mask 做按位或，因为 1 OR x = 1，所以第 k 位必变为 1，其他位与 0 OR 保持不变。这就像在清单上给客户 k 划一个永久勾。

Q3. mask & (mask - 1) 的作用是？

单选题 · easy

  • A.判断 mask 是否为 2 的幂
  • B.清除最低位的 1← 正确答案
  • C.清除最高位的 1
  • D.统计 1 的个数

答案：B。mask 减 1 会让最低位的 1 变 0、其后所有 0 变 1，再与 mask 求与，那些“新冒出来的 1”全被原 mask 的 0 抵消，于是只剩下“原 mask 去掉最低位 1”的结果。此操作常用来判断 2 的幂，但本体作用是清除最低位 1。

Q4. 在 TSP 状态压缩 DP 中，dp[1][0] = 0 表示什么？

单选题 · mid

  • A.从城市 0 出发访问所有城市再回来，总距离为 0
  • B.已访问集合为 {0}、当前停在城市 0，已走距离为 0← 正确答案
  • C.尚未出发，准备访问城市 0
  • D.已访问所有城市、当前停在城市 0 的距离为 0

答案：B。mask=1 的二进制是 001（设第 0 位为 1），表示集合 {0}，即只访问过起点城市 0；第二个下标 0 表示当前停在该城市；距离自然是 0。它是整张 DP 表的“种子状态”，一切转移都从这里发芽。

Q5. 状态压缩 DP 的适用条件有哪些？

多选题 · mid

  • A.集合规模 n 较小（通常 n ≤ 20）← 正确答案
  • B.状态可以自然地表达为“哪些元素已被选择”← 正确答案
  • C.原始数据是无序的巨大数组
  • D.转移依赖集合中最后一个元素与下一个元素的关系← 正确答案

答案：ABD。状态压缩 DP 需要把“集合”塞进整数，因此 n 必须小到 2^n 的状态可存；它天然适合“已选集合 + 最后元素”这类状态结构，例如 TSP 需要知道停在哪个城市、排列计数需要知道队尾是谁。C 中“巨大无数组”恰恰与状态压缩的小规模条件矛盾。

Q6. 用状态压缩 DP 求解 n 座城市的 TSP，时间复杂度是？

单选题 · mid

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

答案：B。状态数为 2^n 种集合 × n 种“当前城市”，每个状态要枚举 n 个可能的上一座城市，因此总复杂度是 O(2^n × n × n) = O(n²·2^n)。相比暴力 O(n!)，当 n=20 时前者约 4 亿次运算，后者约 2.4×10¹⁸ 次，天壤之别。

Q7. 关于枚举子集循环 for (sub = mask; sub; sub = (sub - 1) & mask)，下列说法正确的有？

多选题 · mid

  • A.sub 会依次遍历 mask 的所有非空子集← 正确答案
  • B.外层对所有 mask 枚举子集时，总复杂度为 O(3^n)← 正确答案
  • C.外层对所有 mask 枚举子集时，总复杂度为 O(2^n)
  • D.循环结束后，空子集需要单独处理← 正确答案

答案：ABD。(sub-1) & mask 的核心机制保证 sub 从 mask 本身出发，依次跳过非 mask 的位，精确走遍每个非空子集，最终到 0 终止。每个元素在母集/子集中有三种归属，故总复杂度 O(3^n)；空集被循环排除，需单独考虑。

Q8. 当 n = 20 时，对所有 mask 枚举全部子集的运算量约为？

单选题 · hard

  • A.约 10⁶
  • B.约 10⁸
  • C.约 3.5 × 10⁹← 正确答案
  • D.约 10¹²

答案：C。3²⁰ ≈ 3.486 × 10⁹，这就是 20 个元素全部“母集-子集”组合的总数。这提醒我们，子集枚举型状态压缩 DP 只能承受 n ≤ 15 左右的规模；n=20 时 34 亿次运算已经逼近极限，必须用剪枝或启发式替代。

Q9. 为什么 TSP 的状态压缩 DP 一般不能用滚动数组优化掉 mask 维度？

单选题 · hard

  • A.因为 dp[mask][i] 可能依赖任意更小集合，而不是只依赖“上一层”← 正确答案
  • B.因为 dist 距离矩阵太大，无法放入内存
  • C.因为 n 的值太大，滚动会丢失精度
  • D.因为滚动数组会改变位运算的结果

答案：A。滚动数组的前提是转移只依赖相邻层（如背包依赖容量少一单位）。TSP 中 mask=20（10100）依赖 16（10000）和 4（00100），它们在二进制上并不连续。若要滚动，mask 维度上状态会被错误覆盖，因此只能开满 2^n × n。

Q10. 关于最短哈密顿路径（不需要回到起点）与 TSP 的对比，正确的有？

多选题 · extreme

  • A.哈密顿路径的答案是 min(dp[full][i])，无需加回程← 正确答案
  • B.TSP 的答案是 min(dp[full][i] + dist[i][0])，需要回到起点← 正确答案
  • C.两种问题的状态定义 dp[mask][i] 与转移方程完全相同← 正确答案
  • D.哈密顿路径无法用状态压缩 DP 求解

答案：ABC。两者都是“恰好访问每座城市一次”，区别只在最后是否回起点，所以状态定义和转移方程完全共享，仅最终答案差一条回程边。这也说明 TSP 本质上就是哈密顿路径加一条固定回边，理解其中一个，另一个迎刃而解。