1. 状压DP基础回顾与项目定位
在算法竞赛和编程面试中,动态规划(DP)一直是区分选手水平的分水岭。而状压DP作为DP皇冠上的明珠,其独特的位运算技巧和状态压缩思想,让无数学习者既向往又畏惧。这个系列的第二课,我们将通过三个经典案例的实战解析,带你真正掌握状压DP的应用精髓。
记得我第一次接触状压DP是在准备ACM区域赛时,遇到一道棋盘覆盖问题。当时盯着那些位运算符号看了整整两天,才突然明白为什么要把状态表示为二进制数。这种"顿悟"的体验,正是我想通过本文带给你的——不是死记硬背模板,而是真正理解每个位运算背后的状态含义。
需要模型API调用? 免费领10W Token,多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 案例一:旅行商问题(TSP)的状压解法
2.1 问题重述与状态设计
旅行商问题要求从起点出发,经过所有城市恰好一次后返回,求最短路径。假设有n个城市(n≤20),用邻接矩阵dist[i][j]表示城市间距离。
关键突破点在于:用二进制数的每一位表示某个城市是否被访问过。例如5(101)表示第0和第2个城市已访问。定义dp[mask][u]表示:
- mask:当前已访问城市集合(二进制数)
- u:当前所在城市
状态值:达到这个状态时的最小花费
python复制# 初始化:从0号城市出发
dp[1][0] = 0
for mask in range(1, 1<<n):
for u in range(n):
if not (mask & (1<<u)): continue
for v in range(n):
if mask & (1<<v): continue
new_mask = mask | (1<<v)
dp[new_mask][v] = min(dp[new_mask][v], dp[mask][u] + dist[u][v])
2.2 关键优化技巧
- 预处理合法状态:提前计算每个mask对应的城市数量,当count[mask]==n时跳过
- 对称性剪枝:固定起点为0号城市,减少一半状态空间
- 内存优化:使用滚动数组或按mask中1的个数分层处理
实战经验:当n=16时,完整状态空间是16×2^16=1,048,576。在
