最近重新翻到《算法竞赛进阶指南》0x01位运算这一章的最后一题“最短Hamilton路径”心里还挺感慨。第一次刷到这道题时我在“状态压缩”这个概念前卡了两天后来把位运算和DP拆开揉碎才发现这题几乎是整章位运算的“验收作业”前面学的移位、异或、按位与全在这一题里派上了用场。如果你也是正在啃这本书、或者刚接触状压DP的选手这题值得花一个晚上细品。它能做的不只是让你AC一道题更是帮你在脑子里建立起“用一个整数表示一个集合”的直觉这个直觉后面做TSP、子集枚举、状态DP时全是地基。1. 题目到底在问什么为什么全排列穷举一定行不通1.1 题面解读与核心难点先简单还原一下题目模型给定一张n个点的带权无向图点编号从0到n-1要找一条从0出发、到n-1结束、且每个点恰好经过一次的最短路径。这个“恰好经过一次”就是Hamilton路径的定义。注意它和普通最短路的本质区别普通最短路允许重复经过中间节点Dijkstra、Floyd那套最短路算法天然不适用因为你不知道路径上已经踩过哪些点也就无法约束“不重复经过”。换句话说这题的难点不是“怎么走最短”而是“怎么保证每条路线都不重不漏”。初学者最容易想到的是全排列枚举把中间n-2个点全排列每条排列对应一条从0到n-1的路径算一遍距离取最小。这个方法在n8时确实能跑n10就开始吃力到n12基本就等不起了。题目数据范围直接给到n≤2020!的数量级大约是2.43×10的18次方这个数字大到什么程度呢假设你的程序每秒能枚举1亿种排列跑完所有情况也需要77万年左右。所以枚举这条路从一开始就走不通必须换一种“另存状态”的思考模式。1.2 从阶乘到状态压缩规模决定了思路既然排列数量爆炸那能不能不枚举“顺序”而是枚举“已经走过哪些点”这是状态压缩DP最核心的思路转换。n≤20这个范围非常讲究2的20次方大约是104万每个状态再用O(n)或O(n²)的代价转移总计算量在千万到亿级别对于竞赛环境和现代计算机都是可以接受的。所以问题一下子从“20的阶乘”降到了“2的20次方”这种规模量级的变化就是状态压缩能成立的根因。那“用一个整数表示一个集合”是什么感觉呢你可以把一个整数看成一行二进制的签到表第i位是1表示第i个点已经走过第i位是0表示还没走。比如n5时state0b10101表示集合{0,2,4}因为第0、2、4位是1。这就是状态压缩把原本需要用布尔数组visited[0..n-1]表达的集合信息直接压进了一个int里。而位运算的价值就在于判断、修改这个集合只需要一次一亿分之一秒的位操作不需要循环扫描整个数组。Hamilton路径问题恰好是这种思路最经典的载体。2. 状态设计用26个二进制位装下一张地图2.1 状态定义dp[state][j]到底代表着什么既然要用DP就得先定义状态。二维状态dp[state][j]的含义是当前已经走过的点集合是state并且最后停在点j时从起点0走到这里的最短距离。这里面的state就是那张二进制签到表j就是“当前所在位置”。举个例子dp[0b10011][4]表示已经走过点0、1、4而且当前人在点4这个状态对应的最短路径长度。为什么一定要记录“最后停在哪个点”因为后续路径要继续往下走下一个点的距离取决于当前人的位置。只记录“走过哪些点”是不够的同一组点集合从不同点进来后续代价完全不同。就好比你出差到某个城市同样已经跑完了北京、上海、广州三站但你今天人在上海还是人在广州决定了你明天飞往成都的机票价格和总成本。所以“当前终点”这个信息是DP状态里不可省略的一维。要判断state集合里是否包含某个点j标准写法是if (state j) 1: ...意思是把state右移j位后取最低位如果最低位是1则说明点j在集合里。这是一个高频出现、且初学者容易漏括号的写法建议直接形成肌肉记忆。2.2 状态转移方程从上一个点k走到j假设当前状态是dp[state][j]我们想知道在“走到j之前”这一步人是从哪个点k过来的。既然当前集合是state且包含j那么在到达j之前已经走过的集合必然不包含j也就是state ^ (1 j)。用中文说就是“把state里j这一位从1翻成0”得到上一个时刻的集合prev。那上一个状态的终点k一定在prev集合里且k到j有一条边所以状态转移方程如下dp[state][j] min( dp[state ^ (1 j)][k] w[k][j] )其中k需要遍历所有满足(prev k) 1 1的点。这个方程的意思非常直白倒推一步。当前状态的最优值等于“所有可能的上一步状态的最优值加上从k走到j的那条边的边权”中的最小值。这就是典型的倒推型backward状态转移每算一个状态都把上一个状态的所有可能性穷举一遍。边界初始化也很关键起点只有0号点集合里只有0这一个点人站在0号位所以dp[1][0] 0其余所有状态初始化为无穷大。最终答案是所有点都走过、人停在n-1号点也就是dp[(1 n) - 1][n - 1]。这里(1 n) - 1表示低n位全部为1恰好对应集合{0,1,...,n-1}。2.3 位运算三件套判断、翻转、置位做这题其实只需要掌握三个位运算操作但每一个都用得极其频繁我把它们拆开写清楚。第一判断第j位是否为1(state j) 1。右移j位后原第j位变成最低位再和1做按位与结果就是0或1。这个操作在遍历状态时用来确定“当前节点j是否在集合state里”。第二翻转第j位state ^ (1 j)。异或运算的规则是同0异1因为第j位原本为1异或1后变成0而其他位异或0保持原样所以这个式子就是“把第j位从1变成0”。反过来如果第j位原本是0这个操作会把它变成1。在倒推型DP中我们用它得到“去掉当前节点后的上一状态”。第三置第j位为1state | (1 j)。按位或的结果是只要某一位有一个1就为1所以这个操作专门用来“在集合中新增一个点”。如果你写的是正向型DP从已有状态向外扩展新节点这绝对是最常用到的操作。这三个操作合在一起就是算法竞赛里处理集合DP的“指法基础”。练这题时我不建议直接把代码背下来建议自己在纸上把state从0到31都手写一遍二进制然后用位运算判断每个点是否在集合里练上十几分钟后状态压缩会变得非常自然。3. 实操过程与Python完整实现3.1 思路清晰的正向写法先给一个最贴合直觉的正向forwardDP写法。它从当前状态出发尝试往集合里加入一个还没走过的点j用当前值去更新下一个状态。这种写法很适合刚上手状态压缩DP的读者因为每一步都是“当前集合→新集合”的扩张式思考不容易把转移方向搞反。import sys def solve(): data sys.stdin.buffer.read().split() if not data: return n int(data[0]) w [] idx 1 for _ in range(n): w.append(list(map(int, data[idx:idx n]))) idx n INF 10 ** 9 size 1 n dp [[INF] * n for _ in range(size)] dp[1][0] 0 # 集合中只有点0当前在点0 for state in range(size): for k in range(n): # 点k必须已经在当前集合中才能作为“当前所在点” if not (state k) 1: continue cur dp[state][k] if cur INF: continue # 尝试走向一个不在当前集合中的点j for j in range(n): if (state j) 1: continue nxt state | (1 j) val cur w[k][j] if val dp[nxt][j]: dp[nxt][j] val print(dp[size - 1][n - 1]) if __name__ __main__: solve()代码里最需要留意的一点是更新语句dp[state | (1 j)][j]。它表达的是“把j加入集合并且人停在j”的新状态而j就是新状态里的最后节点。这个写法里三个位运算全用上了(state k) 1判断k在不在集合里(state j) 1判断j在不在集合里state | (1 j)把j加入集合。3.2 用一个小样例手工推演为了确认代码不是“玄学通过”我们手工走一遍n4的例子。假设邻接矩阵如下边权值0-120-250-391-231-362-31最短路径是0 → 1 → 2 → 3总距离2 3 1 6。我们挑几个关键状态验证。初始化dp[1][0]0state1表示集合{0}。从state1出发k0遍历j1、2、3分别得到dp[3][1]2、dp[5][2]5、dp[9][3]9。state3二进制011表示集合{0,1}k可以取0或1。由于dp[3][0]是INF主要看k1时j2得到dp[7][2]dp[3][1]35j3得到dp[11][3]dp[3][1]68。最终state15二进制1111j3时考虑k2dp[7][2]w[2][3]516而k1dp[11][1]如果是INF则忽略k0也是INF所以dp[15][3]6和手工答案一致。这样的推演过程建议你自己也在草稿纸上跑一遍因为只有自己写过一轮状态编号、二进制展开、位运算判断后才能真正理解为什么状态从1到15枚举就足够了为什么prev状态一定比当前状态小、能够保证DP的无后效性。3.3 性能优化Python也能扛住n20Python版的三重循环在n20时最坏会跑大约 2^20 × 20 × 20 ≈ 4亿次内层操作。裸写法在普通机器上可能要十几秒放在在线评测里容易卡超时。实测下来有下面几个能有效压时间的优化手段单独用每一个都能带来明显提升组合使用后n20一般能压到几秒内。第一个优化是跳过无效状态。代码里已经写了if not (state k) 1: continue和if cur INF: continue。尤其是后者因为大部分状态根本不可达或者尚未更新直接用无穷大判断砍掉能省掉大量无效的内层计算。第二个优化是局部变量引用。Python访问局部变量比访问全局变量快很多把dp、w、n这些循环里高频访问的名字绑定到局部能减少属性查找的开销。第三个优化是读入用sys.stdin.buffer.read一次性读入全部数据再按块切片比反复调用input()快得多这在n20时虽然影响不大但却是竞赛Python题的通用习惯。第四个优化空间更大固定起点0后所有有效状态里一定包含点0也就是说state必须是奇数。于是主循环可以写成range(1, size, 2)直接把一半状态砍掉再把内部循环里所有if not (state k) 1的判断做前置过滤。配合PyPy跑实践中n20的数据一般能在1到2秒内出结果。如果你不想牺牲代码可读性也可以只加前两个优化大部分题已经能过。4. 常见问题与排查技巧实录4.1 初始化、边界与答案位置最容易错这题出错率最高的一块就是初始化。dp[1][0] 0是必须写对的第一行很多人习惯性把整个dp都设成0然后答案永远算出来是0或者把dp[0][...]当成合法状态结果输出一堆INF。另一个容易错的位置是最终答案必须是dp[(1 n) - 1][n - 1]而不是min(dp[(1 n) - 1])。因为题目强制终点是n-1如果终点不固定才是对所有j取min。但本书这题的题意是固定的所以别多想取最后一个格子的值就对了。还有一种情况是题目给的图可能不是完全图点之间可能不存在边。这时邻接矩阵对应位置往往给一个很大的数或0你需要按题目约定处理。如果存在不连通的情况答案可能是INF输出什么要看题面但多数题保证有解不用特别处理。做其他变体时要注意INF不能取得太小不然真实路径可能被INF“挡住”建议取10的9次方以上。4.2 位运算优先级与写反状态位运算的优先级是个隐藏地雷。state j 1在没有括号时会被解释成(state j) 1因为位移运算符的优先级高于按位与这个还好。但如果你写state (1 j) 0比较运算符的优先级高于实际会变成state ((1 j) 0)结果完全不对。所以只要涉及位运算和比较运算混合一律加括号这是最保险的习惯。还有一类错误是把state ^ (1 j)当成“加入j”。其实异或的效果是“翻转第j位”只有确定state已经包含j时用它才是“去掉j”只有确定state不包含j时用它才是“加入j”。如果你在前向转移里用了state ^ (1 j)来尝试加入j而state恰好又已经包含了j就会把j从集合里删掉产生一个完全错误的状态。所以前向更新统一用state | (1 j)后向回退统一用state ^ (1 j)这俩别混。4.3 性能踩坑二维数组初始化陷阱Python里初始化二维数组有个经典坑dp [[INF] * n] * (1 n)这种写法会创建n个指向同一行的引用改一个元素会带动所有行一起变结果答案错得莫名其妙。正确写法是[[INF] * n for _ in range(1 n)]每一行都是独立列表。这个坑我在教朋友调题时见过好多次建议直接养成用列表推导式初始化的习惯。此外如果n比较大、内存吃紧也可以考虑把dp按state维度压缩成字典但Python字典查找比列表慢得多我做测试时发现基本还是二维列表更快。对于n20二维列表总共约2千万个整数项每个Python整数对象占28字节左右内存大概600MB有点顶不住。一个备选方案是用array(i)或者只存储需要的数据类型来降低内存但对大多数人来说在竞赛场景直接用PyPy跑、内存限制给到512MB时通常能过。如果真遇到内存很紧的题可以想想能不能把状态维缩小比如通过对称性或者路径压缩不过这是后话了。5. 这类题目的举一反三状态压缩DP的通用思路5.1 一串问题其实都是同一道题“每个点恰好经过一次”这种排列型约束在算法题里出现频率非常高。旅行商问题TSP几乎是Hamilton路径的孪生兄弟区别只是起点不固定、最终要回到起点此时初始化改成dp[1 i][i] 0答案改成min(dp[(1 n) - 1][i] w[i][0])。再比如“安排任务的最短完成时间”“给定一些钥匙和门的最短路”“子集划分问题”很多都能归结到同一个套路用一个整数表示集合用dp[state][i]表示某种“当前集合和当前终点”的组合状态。当你遇到n≤20、需要处理子集或排列的题第一反应就应该是“这题可能要用状压DP”。这和看到n1e5就想到二分、线段树一样属于算法竞赛里的条件反射。有了Hamilton路径打底再看二进制枚举子集的代码会发现里面到处都是for sub state; sub; sub (sub - 1) state这类位运算操作你已经不需要再去翻资料了。5.2 我在刷这部分时的几条心得第一个心得是写DP先写状态转移图不要急着写代码。Hamilton路径的状态转移是“当前状态倒推上一个状态”画出类似“当前state和j → 上一个state和k”的关系后代码只是翻译。第二个心得是先用小n把样例跑通再优化。n4的样例能帮你验证逻辑n8的随机数据能帮你确认没有数组越界和初始化错误最后才考虑n20的优化。第三个心得是位运算代码最好在草稿纸上有二进制对照。比如看到state13能立刻反应出0b1101和集合{0,2,3}的对应关系而不是每次在脑子里换算半天这个熟练度刷上十几道状压题自然就有了。5.3 如果要继续扩展状态压缩不止这一种形态Hamilton路径是状态压缩DP的入门题但不是终点。再往后你还会遇到集合上的博弈必胜态/必败态压缩、轮廓线DP插头DP中用二进制表示轮廓线状态、子集卷积高维前缀和配合位运算等等。尤其值得一提的还有“子集枚举”这个方向当需要枚举某个集合的所有子集时for sub in range(state, 0, -1): sub state这种倒序枚举方式配合位运算可以把很多本来O(3^n)的枚举优化到能跑的范围。这些技巧本质上都是在同一套位运算体系下演化出来的Hamilton路径这道题如果吃透了后面这些概念理解起来会顺畅很多。另外如果你觉得Python在大数据下还是吃力可以试试在代码最外层套上PyPy而不是CPython提交同样的三重循环经常能快3到5倍。当然平时自己刷题练习时我还是建议用CPython跑因为这样更贴近真实工程环境也能逼自己想清楚哪些地方是真正的计算瓶颈而不是无脑把所有东西都丢给编译器优化。