引言在动态规划中状态的表示直接影响算法的可行性与效率。当问题涉及“集合覆盖”“子集选择”“排列顺序”等组合对象时直接用数组下标表示集合往往需要指数级空间。状态压缩DP简称状压DP利用二进制位来表示集合的状态0/1表示元素是否在集合中从而将复杂的状态空间压缩为一个整数再用DP递推求解。如果把普通DP比作“用表格填数字”那么状压DP就是“用二进制密码本记录集合一次位运算就完成状态转移”—— 它以位的代价换取了表达指数级组合的能力。前置知识位运算基础与、|或、^异或、左移、右移、~取反。常用位运算技巧取出第i位(s i) 1将第i位设为1s | (1 i)将第i位设为0s ~(1 i)枚举所有子集for (int sub s; sub; sub (sub-1) s)判断是否是2的幂(s (s-1)) 0动态规划基础状态定义、转移方程、初始条件、答案提取。核心思想状压DP的核心在于将集合用整数表示整数的二进制位对应集合中的元素通常元素个数 n ≤ 20因为 2^n 状态数可接受。例如n 4 时整数50101二进制表示第0和第2个元素在集合中。状态总数最多 2^n当 n20 时约 100 万可以接受。典型模型旅行商问题TSPdp[mask][u]表示已经访问过的城市集合为 mask当前在城市 u 时的最短路径。覆盖问题dp[mask]表示覆盖集合 mask 所需的最小代价。子集枚举DPdp[mask] min(dp[mask], dp[sub] cost(sub ^ mask))等。形象地讲状压DP就是把“哪些元素用过了”这个信息写在了一个整数的二进制位里。转移时不再需要遍历元素列表而是直接用位运算判断、取反、取子集。算法步骤以TSP为例状态定义dp[mask][u] 已经访问过集合 mask 中的城市最后停留在城市 u 的最短距离。初始化dp[1 start][start] 0其余为无穷大。转移对于每个状态(mask, u)尝试走到下一个未访问的城市 vif ((mask v) 1) 0: new_mask mask | (1 v); dp[new_mask][v] min(dp[new_mask][v], dp[mask][u] dist[u][v]);答案min(dp[(1n)-1][u] dist[u][start])回到起点的最小环路。代码框架int n; int dist[N][N]; int dp[1N][N]; int tsp() { memset(dp, 0x3f, sizeof(dp)); dp[1][0] 0; // 从0号城市出发 for (int mask 1; mask (1n); mask) { for (int u 0; u n; u) if ((mask u) 1) { for (int v 0; v n; v) if (!((mask v) 1)) { int new_mask mask | (1 v); dp[new_mask][v] min(dp[new_mask][v], dp[mask][u] dist[u][v]); } } } int ans INF; int full (1 n) - 1; for (int u 0; u n; u) { ans min(ans, dp[full][u] dist[u][0]); } return ans; }复杂度与性质特征说明时间复杂度O(2^n * n²) 或 O(2^n * n) 取决于内层循环空间复杂度O(2^n * n)适用规模n ≤ 20 通常可接受n25 时 2^25≈3300万需优化常用优化预处理合法转移、只遍历包含u的状态、使用滚动数组性质状压DP常用于NP-hard问题的精确求解如TSP、集合覆盖对于小规模数据非常有效。可以与递推、记忆化搜索结合。可以利用对称性、剪枝减少状态。子集卷积、快速沃尔什变换FWT可用于加速某些状压DP的转移。例题与解析例题1旅行商问题TSPLuogu P1171题目描述有 nn ≤ 20个城市给出城市间的距离矩阵对称不满足三角不等式。求从城市0出发访问所有城市恰好一次并返回城市0的最短路径长度。输入示例4 0 2 6 5 2 0 4 4 6 4 0 2 5 4 2 0输出示例13解题思路直接使用上述TSP的状压DP模板注意距离矩阵可能不是对称的但题目保证对称。注意边界条件从0出发最终回到0。解析状态总数 2^n * n ≈ 2^20 * 20 ≈ 2000万在C中勉强可过需要常数优化。可以使用滚动数组只保留当前mask的dp值但转移需要枚举u和v无法完全滚动。常用的优化是只对mask中已经访问过的u进行转移并且预先存储每个mask有哪些u通过lowbit迭代。或者使用递推顺序for mask从1到full内层for u枚举再内层for v枚举未访问点。例题2玉米田Luogu P1879题目描述农夫有一块 n×mn,m ≤ 12的网格某些格子是贫瘠的不能种玉米某些是肥沃的。要种玉米要求相邻上下左右的格子不能同时种。求有多少种种植方案模100000000。输入示例2 3 1 1 1 0 1 0输出示例9解题思路每一行的种植状态可以用一个 m 位二进制数表示1表示种0表示不种。预处理该行自身是否合法不能有相邻的1且不能种在贫瘠格子上。相邻两行状态不能有在同一列都是1即state prev_state 0。定义dp[i][state]表示前 i 行第 i 行状态为 state 的方案数。转移dp[i][state] sum(dp[i-1][prev])其中(state prev) 0且两者都合法。解析总状态数最多 2^12 4096行数12复杂度 O(n * 2^m * 2^m) ≈ 12 * 4096 * 4096 ≈ 2亿稍大但通过预处理合法状态可优化。合法状态数量远小于 2^m因为相邻不能为1斐波那契数约为 2^m / φ^m。典型轮廓线DP插头DP的简化版。例题3互不侵犯Luogu P1896题目描述在 n×nn ≤ 9的棋盘上放 k 个国王国王的攻击范围是周围8个格子。求互不攻击的摆放方案数。输入示例3 2输出示例16解题思路每一行状态用二进制表示国王的放置情况。需要预处理一行内不能有相邻的国王state (state1) 0。相邻两行之间不能有冲突(state prev) 0且(state (prev1)) 0且(state (prev1)) 0。定义dp[i][state][c]表示前 i 行第 i 行状态为 state已经放置了 c 个国王的方案数。转移时累加前一行的合法状态增加国王数。解析相比玉米田多了“对角线”限制以及国王数量的维度。n9状态最多 2^9512国王数最多 81DP数组大小 10*512*82 ≈ 42万可接受。拓展轮廓线DP插头DP处理棋盘上的连通性问题如铺砖、哈密顿路径状态是轮廓线上的连通性表示括号序列或最小表示法。子集DPSOS DP用于快速处理子集求和、子集最值等问题复杂度 O(n·2^n)。DP on subsets with FWT利用快速沃尔什变换加速子集卷积用于某些集合划分问题。记忆化搜索状态压缩对于不确定的转移顺序用DFS备忘录代替递推。总结状压DP将组合问题的指数级可能性压缩在整数位中配合位运算使得原本无法处理的集合划分、子集选择问题在小规模上变得可行。它是算法竞赛中解决NP-hard问题的经典武器也是理解更复杂DP如插头DP、子集卷积的基础。