1. 项目概述当动态规划遇上二进制魔法如果你写过一些涉及“选择”或“组合”的算法题比如经典的旅行商问题TSP、棋盘覆盖问题或者一些需要记录“哪些物品已被选取”的背包问题变种你大概率会碰到一个令人头疼的瓶颈状态空间爆炸。传统的动态规划DP用数组下标来表示状态但当状态本身是一个集合——比如一个由n个元素构成的子集——时直接用一个维度来表示这个集合状态数量会高达2^n对于n20的情况那就是百万级别n30更是直接突破十亿无论是时间还是空间都难以承受。这时候就需要请出我们今天的主角状态压缩动态规划一种用二进制数的每一位来“压缩”表示集合中元素存在与否的“魔法”技巧。这不仅仅是C竞赛和面试中的高频考点更是解决一类复杂组合优化问题的核心利器。它的核心思想非常直观既然集合的每个元素只有“在”或“不在”两种状态那么一个n位的二进制数其每一位的0或1不就天然对应了集合中每个元素的状态吗通过位运算我们可以在常数时间内完成集合的增删、合并、判断等操作将原本庞大的状态表示压缩到一个整数里从而让DP方程得以高效递推。接下来我将带你深入这个“二进制魔法”的世界从核心思想、位运算工具箱到经典模型和实战避坑手把手教你掌握这门让算法效率产生质变的技术。2. 状态压缩DP的核心思想与位运算工具箱2.1 为什么需要状态压缩让我们从一个具体场景开始理解。假设有一个任务分配问题有5个任务和3个工人每个工人可以完成其中某些任务且每个任务只能由一个工人完成。我们需要计算所有任务都被完成的不同分配方案数。一个最朴素的想法是用一个三维DP数组dp[i][j][k]其中i、j、k分别表示三个工人各自完成的任务集合。但如何表示一个“集合”呢如果用布尔数组或vectorbool不仅比较起来麻烦更无法直接作为数组下标。状态压缩的核心动机就在这里将高维的、结构化的状态如集合、排列映射到一个低维的、线性的编码通常是一个整数从而能够用数组进行存储和递推。二进制因其每一位的独立性0/1和位运算的高效性成为这种编码的绝佳选择。2.2 位运算你的状态操作瑞士军刀在状态压缩DP中位运算不是可选项而是必须熟练掌握的基本功。下面这个表格总结了最核心的几种操作及其在集合语义下的含义假设我们有一个n位二进制数state最低位为第0位代表第0个元素操作符号示例 (state 1011₂, n4)集合语义关键要点判断元素i是否在集合中state i 1(1011 2) 1 0查询第2个元素是否存在先右移i位使目标位到最低位再与1进行与操作。将元素i加入集合state | (1 i)1011 | (12) 1111加入第2个元素1i生成一个只有第i位是1的掩码通过或运算置位。将元素i从集合中移除state ~(1 i)1011 ~(11) 1001移除第1个元素~(1i)生成一个第i位为0、其余位为1的掩码通过与运算清零。切换元素i的状态state ^ (1 i)1011 ^ (10) 1010取反第0个元素的状态异或运算在0/1之间翻转。判断集合B是否是集合A的子集(B A) BA1011, B1001 成立B的所有元素都在A中核心是B A的结果如果还是B说明B的每个1在A中对应也是1。枚举集合S的所有非空子集for(sub S; sub; sub (sub-1) S)S1011 将循环得到1011, 1010, 1001, ...高效遍历子集这是一个经典技巧(sub-1) S确保了每次得到的都是S的前一个子集复杂度为O(2^k)k是S中1的个数。获取集合S的补集在全集U内(~S) US1011, U(14)-11111 0100全集U中不在S里的元素非常重要直接对S取反~S会得到高位全是1的负数必须用全集U进行掩码操作限定在有效位内。注意在实际编码中尤其是C中直接对整数进行按位取反~操作会作用于该整数类型的所有位通常是32或64位。对于一个仅用低n位表示集合的整数state~state的高位第n位及以上也会变成1这通常不是我们想要的。因此计算补集时务必使用(~state) ((1 n) - 1)来将高位清零其中(1 n) - 1就是全集U的二进制表示低n位全是1。2.3 状态设计从问题到二进制映射设计状态是DP的灵魂对于状态压缩DP更是如此。通常状态dp[s]中的s这个整数直接编码了“当前已完成的选择”这个集合。例如旅行商问题TSPdp[s][i]表示已经访问过的城市集合为s且当前位于城市i时的最短路径长度。这里s的每一位表示一个城市是否已被访问。棋盘覆盖/骨牌铺设问题dp[i][s]表示处理到第i行时该行的覆盖状态为s例如用1表示该格子已被上一行的骨牌占据0表示空闲。状态转移需要考虑当前行s与下一行状态s_next的兼容性。任务分配/工作调度dp[s]表示已经分配的任务集合为s时某种指标如最小成本、最大收益的最优值。设计的关键在于找到问题中那个“选择”的维度并将其所有可能的组合用二进制位表示。这个被压缩的维度通常是导致状态数指数级增长的元凶。3. 经典模型深度解析与C实现理解了思想和工具我们通过两个最经典的模型来具体感受状态压缩DP的威力。我会提供详细的C代码实现并解释每一行代码背后的意图。3.1 模型一旅行商问题TSPTSP是状态压缩DP的“名片级”问题。问题描述有n个城市给出任意两城市间的距离求从某个城市出发恰好访问每个城市一次并回到起点的最短路径。状态设计设城市编号为0到n-1。定义dp[s][i]s是一个n位二进制数表示已经访问过的城市集合i表示当前所在的城市。dp[s][i]的值表示从起点出发访问完集合s中的所有城市最后停在城市i所走过的最短路径长度。初始状态dp[1start][start] 0表示从起点出发只访问了起点自身距离为0。其他状态初始化为无穷大。状态转移我们考虑最后一步是怎么走到i的。一定是先从某个状态dp[s_without_i][j]即访问了除i外的城市集合s_without_i且停在城市j然后从j走到i。因此转移方程为dp[s][i] min(dp[s][i], dp[s_without_i][j] dist[j][i])其中s_without_i s ^ (1 i)即从集合s中移除城市i。并且需要满足(s_without_i j) 1为真即城市j在集合s_without_i中。最终答案访问所有城市后回到起点start即dp[(1n)-1][start]。如果问题不要求回到起点则答案是min(dp[(1n)-1][i] dist[i][start])即最后在任何城市结束再考虑回到起点的距离。C实现关键代码与注释#include vector #include cstring #include algorithm using namespace std; const int INF 0x3f3f3f3f; // 用一个较大的数代表无穷大 int tsp(int n, vectorvectorint dist, int start) { int state_num 1 n; // 状态总数 2^n vectorvectorint dp(state_num, vectorint(n, INF)); // 初始化从起点开始 dp[1 start][start] 0; // 遍历所有状态s for (int s 0; s state_num; s) { // 遍历当前状态s下可能所在的城市i for (int i 0; i n; i) { // 如果状态s中不包含城市i则dp[s][i]是无效状态跳过 if ((s i 1) 0) continue; // 如果dp[s][i]还是无穷大说明尚未可达也无法从它转移出去跳过 if (dp[s][i] INF) continue; // 尝试从当前状态(s, i)转移到下一个状态 // 枚举下一个要去的城市j for (int j 0; j n; j) { // 如果城市j已经在集合s中跳过避免重复访问 if (s j 1) continue; int next_s s | (1 j); // 将j加入集合 dp[next_s][j] min(dp[next_s][j], dp[s][i] dist[i][j]); } } } // 计算回到起点的最短路径 int full_state (1 n) - 1; // 全集所有城市都访问过 int ans INF; for (int i 0; i n; i) { // 最终状态是访问完所有城市(full_state)且最后停在i // 需要从i再回到起点start if (dp[full_state][i] ! INF dist[i][start] ! INF) { ans min(ans, dp[full_state][i] dist[i][start]); } } return ans INF ? -1 : ans; // 如果无解返回-1 }注意事项与性能分析时间复杂度为O(n² * 2^n)空间复杂度为O(n * 2^n)。当n20时2^20 ≈ 1e6n²400总运算量约4e8在优化良好的C中通常可在1秒左右完成。n22将是极限约1.8e9次运算。内存优化有时可以使用滚动数组或者用dp[s]只存储一个最优值但TSP的标准解法需要记录最后位置i。初始化dist矩阵时注意处理不连通的情况通常用INF表示。3.2 模型二棋盘覆盖问题骨牌铺设这类问题形式多样比如用1x2的骨牌覆盖NxM的棋盘有些格子禁止放置。这也是状态压缩DP的经典战场。问题简化假设有一个N行M列的棋盘某些格子有障碍。用1x2的骨牌可以横放或竖放覆盖所有非障碍格子且骨牌不重叠求方案总数。M通常较小12N较大。状态设计按行进行DP。定义dp[i][s]表示处理完前i-1行且第i行的状态为s时的方案总数。这里s的每一位表示第i行对应列格子的“覆盖状态”。如何定义“覆盖状态”是本题关键。一个常见的定义是用1表示这个格子被第i-1行延伸下来的竖放骨牌“占据”即当前行这个格子不能放骨牌的起点用0表示这个格子空闲可以由当前行开始放置骨牌。状态转移从dp[i-1][s_prev]转移到dp[i][s_curr]。我们需要枚举第i行在上一行状态为s_prev的前提下所有可能的放置方式从而得到第i行的状态s_curr。转移过程这是一个DFS搜索过程。我们用递归函数dfs(col, s_prev, s_curr, next_s)来枚举当前行第i行的放置col: 当前处理到的列号。s_prev: 上一行的状态二进制。s_curr: 当前行已生成的状态二进制。next_s: 当前行放置骨牌后对下一行i1行造成的影响状态即哪些格子被当前行竖放的骨牌“占据”。递归基当col M时说明当前行放置完毕可以进行转移dp[i][next_s] dp[i-1][s_prev]。递归过程如果s_prev在第col位是1说明上一行有竖牌占了这个位置那么当前行这个位置必须被“占据”不能放新骨牌。所以直接递归dfs(col1, s_prev, s_curr, next_s)。否则当前位置空闲有两种选择竖放骨牌如果当前不是最后一行保证竖放有效且当前行s_curr的第col位是0未被占据则可以竖放。这会将next_s的第col位置为1影响下一行然后递归dfs(col1, s_prev, s_curr, next_s | (1col))。横放骨牌如果当前列col不是最后一列且当前位置和右侧位置都空闲即s_prev和s_curr的第col和col1位都是0则可以横放。这会将s_curr的第col和col1位置为1表示当前行这两个位置被占用然后递归dfs(col2, s_prev, s_curr | (3col), next_s)。3col生成了一个连续两位为1的掩码。C实现关键代码与注释#include vector #include cstring using namespace std; long long solve(int N, int M, vectorvectorbool blocked) { int state_num 1 M; vectorvectorlong long dp(N 1, vectorlong long(state_num, 0)); dp[0][0] 1; // 初始状态第0行虚拟行状态为0 // 预处理每行的障碍掩码方便判断 vectorint block_mask(N 1, 0); for (int i 1; i N; i) { for (int j 0; j M; j) { if (blocked[i-1][j]) { // 假设blocked是0-indexed block_mask[i] | (1 j); } } } // DFS函数枚举当前行的所有放置方式 functionvoid(int, int, int, int, int) dfs [](int row, int col, int s_prev, int s_curr, int next_s) { if (col M) { // 当前行放置完毕且不能有障碍 if ((s_curr block_mask[row]) 0) { dp[row][next_s] dp[row - 1][s_prev]; } return; } // 如果上一行的这个位置是1被竖牌占据则当前位置必须“被占据” if ((s_prev col) 1) { dfs(row, col 1, s_prev, s_curr, next_s); return; } // 尝试竖放 (1x2) // 当前行当前位置空闲且不是最后一行竖放要延伸到下一行 if (row N ((s_curr col) 1) 0) { // 竖放会影响下一行所以next_s的col位置1 dfs(row, col 1, s_prev, s_curr, next_s | (1 col)); } // 尝试横放 (2x1) // 需要当前位置和右侧位置都空闲且不在最后一列 if (col 1 M ((s_prev col) 1) 0 ((s_prev (col 1)) 1) 0 ((s_curr col) 1) 0 ((s_curr (col 1)) 1) 0) { // 横放占用当前行的两个位置 dfs(row, col 2, s_prev, s_curr | (3 col), next_s); } }; for (int i 1; i N; i) { for (int s_prev 0; s_prev state_num; s_prev) { if (dp[i - 1][s_prev] 0) continue; // 无效状态跳过 // 上一行的状态s_prev不能与障碍冲突 if ((s_prev block_mask[i - 1]) ! 0) continue; // 开始枚举当前行(i)的所有可能放置 dfs(i, 0, s_prev, 0, 0); } } // 最终答案处理完第N行且第N行没有对下一行造成任何“占据”即状态为0 return dp[N][0]; }核心要点解析状态定义的精髓s_prev中的1表示“上一行有竖牌下来占据了这个位置”所以当前行这个位置不能作为新骨牌的起点。s_curr中的1表示“当前行放置的骨牌横放或作为竖放的起点占用了这个位置”。next_s中的1表示“当前行放置的竖牌将占据下一行的这个位置”。DFS枚举的必要性由于一行中骨牌的放置方式有多种组合横放、竖放、不放且相互影响无法用简单的循环直接计算必须通过DFS来生成所有合法的放置方案。障碍处理通过block_mask记录每行障碍位置。在状态转移的两个地方需要检查一是上一行的状态s_prev不能覆盖障碍因为障碍格不能被占据二是当前行生成的状态s_curr不能覆盖障碍因为障碍格不能被骨牌占用。复杂度状态数O(N * 2^M)对于每个状态s_prevDFS枚举当前行所有放置方式最坏情况下是O(2^M)尽管通过剪枝远小于。总复杂度约为O(N * 2^M * 2^M) O(N * 4^M)。当M12时4^1216M再乘以N可能上千需要优化或确保N不太大。实际中由于DFS剪枝通常可解。4. 实战技巧与避坑指南掌握了模型但在实际编码和解题中还有很多细节和技巧决定了成败。下面是我从大量实战中总结出的经验。4.1 空间优化滚动数组状态压缩DP的状态数通常是2^n当n较大时如n20dp[120][n]的空间可能达到数百MB容易导致内存超限。一个常见的优化是使用滚动数组。因为很多DP的转移只依赖于上一层的状态。以棋盘覆盖为例dp[i][s]只依赖于dp[i-1][*]。我们可以只定义两个一维数组dp_curr和dp_next分别代表当前行和下一行的状态值。vectorlong long dp_curr(state_num, 0), dp_next(state_num, 0); dp_curr[0] 1; // 初始化第0行 for (int i 1; i N; i) { fill(dp_next.begin(), dp_next.end(), 0); // 清空下一行 for (int s_prev 0; s_prev state_num; s_prev) { if (dp_curr[s_prev] 0) continue; // ... 进行DFS枚举将结果累加到dp_next中 ... // dfs(i, 0, s_prev, 0, 0, dp_curr, dp_next); } swap(dp_curr, dp_next); // 滚动到下一行 } // 最终答案在dp_curr[0]中这样空间复杂度从O(N * 2^M)降到了O(2^M)。4.2 时间优化预处理合法状态与转移在像棋盘覆盖这类问题中对于每个s_prev我们都需要DFS枚举所有可能的s_curr和next_s。这个枚举过程可能重复很多次。一个有效的优化是预处理。我们可以预先计算出对于任意一个上一行状态s_prev所有可能的(s_curr, next_s)对。这样在DP主循环中就可以直接遍历这些预处理的转移对而无需每次进行DFS。// 假设M是固定的 vectorvectorpairint, int trans(1 M); // trans[s_prev] 存储所有合法的(s_curr, next_s) // 预处理函数类似之前的DFS但只生成不计算dp值 functionvoid(int, int, int, int) dfs_pre [](int col, int s_prev, int s_curr, int next_s) { if (col M) { trans[s_prev].push_back({s_curr, next_s}); return; } // ... 同样的放置逻辑 ... }; for (int s_prev 0; s_prev (1 M); s_prev) { dfs_pre(0, s_prev, 0, 0); } // DP主循环 for (int i 1; i N; i) { fill(dp_next.begin(), dp_next.end(), 0); for (int s_prev 0; s_prev state_num; s_prev) { if (dp_curr[s_prev] 0) continue; for (auto [s_curr, next_s] : trans[s_prev]) { // 检查障碍 if ((s_curr block_mask[i]) ! 0) continue; dp_next[next_s] dp_curr[s_prev]; } } swap(dp_curr, dp_next); }预处理将DFS的复杂度从DP的每层每状态都执行一次提前到了初始化阶段只执行一次大大加速了DP过程。4.3 调试技巧状态可视化二进制状态对人来说不直观。调试时将整数状态s打印成二进制字符串非常有用。void printState(int s, int n) { for (int i n-1; i 0; --i) { cout ((s i) 1); } cout endl; }更进一步可以编写一个函数根据问题语义来解释状态。例如在TSP中打印出状态s代表了访问了哪些城市。4.4 常见错误与排查清单位运算优先级陷阱和|的优先级低于和!。if (s 1 0)会被解释为if (s (10))这永远是if (s 0)即false。正确的写法是if ((s 1) 0)。强烈建议在涉及位运算和比较的判断中一律加上括号。补集计算未限定范围如前所述~state会反转所有位。计算在n位全集内的补集一定要用(~state) ((1n)-1)。状态初始化错误DP的初始状态通常只有一个或几个是有效的如dp[1start][start]0其他应设为“无效值”如INF或0取决于问题是求最大/最小还是计数。忘记初始化或初始化错误会导致结果不正确。遍历顺序错误状态压缩DP的遍历顺序必须保证在计算dp[s][i]时它所依赖的子状态dp[s_without_i][j]已经被计算出来。对于集合状态s通常采用递增的顺序遍历s从0到(1n)-1。这是因为从一个集合移除元素得到的集合其二进制表示一定比原集合小如果元素编号是顺序的。所以递增遍历是安全的。数组越界状态总数是1n数组大小应至少为此。如果状态中包含了“当前所在位置”等额外维度总状态数是(1n) * n确保数组开够了。整数溢出方案计数类问题结果可能非常大务必使用long long甚至__int128或高精度。在中间计算dp[next_s] dp[s_prev]时也要注意溢出。5. 从经典到变种思路扩展与问题建模掌握了经典模型很多复杂问题都可以被归结或转化为状态压缩DP。关键在于如何将问题抽象成“集合选择”模型。变种1带权集合覆盖问题有n个任务m个工人。每个工人能完成一个任务集合skills[i]用二进制表示雇佣他有成本cost[i]。求覆盖所有任务的最小总成本。这看似是集合覆盖但可以用状态压缩DP解决。定义dp[s]为覆盖任务集合s的最小成本。初始化dp[0]0其他为INF。对于每个工人i其技能掩码为mask则状态转移为dp[s | mask] min(dp[s | mask], dp[s] cost[i])。最终答案是dp[(1n)-1]。复杂度O(m * 2^n)。变种2图着色与最大团问题给定一个无向图求最大的顶点集合使得该集合内任意两点都有边相连最大团。这是一个NP难问题但n较小50时可用状态压缩DP在子图上求解。一种折半搜索Meet-in-the-Middle的思路将顶点集分成两半A和B。预处理出B部分所有子集是否是团以及其大小。然后对于A部分的每个子集s_a检查它是否是团如果是找出在B部分中所有与s_a中每个顶点都相连的顶点集合adj_set那么B中所有是adj_set子集的团都可以与s_a合并。这需要用到超集枚举或SOS DPSum Over Subsets DP来快速查询B部分中给定集合adj_set的所有子集中团的最大大小。这展示了状态压缩DP与其他高级技巧的结合。变种3资源分配与轮廓线DP棋盘覆盖问题是“按行DP”的典范。更一般地当问题是在二维网格上进行并且当前行的决策只与上一行有限格子的状态有关时可以使用轮廓线DP。它不再以整行为状态而是以一条“轮廓线”穿过网格的格子状态为状态。这条轮廓线通常包含了当前处理格子的左上角一些格子的状态。这进一步压缩了状态适用于某些按行DP状态数仍然过多的问题。建模心法识别“决策单元”问题中哪些元素是需要被选择、放置或覆盖的这些元素构成集合。定义“状态”当前已经完成了哪些决策这些决策的结果如何用一个紧凑的形式二进制表示寻找“转移”如何从已知的小规模决策结果子状态通过做一个新的决策扩展到更大规模的状态转移的代价或收益是什么确定“顺序”如何遍历状态确保子状态先于父状态被计算通常是按照集合大小二进制中1的个数递增的顺序。状态压缩DP的精髓在于它让我们能用计算机最擅长的整数运算和位操作去优雅地处理那些原本需要复杂数据结构才能表示的组合状态。这种将组合数学问题“编码”成整数问题的能力是算法竞赛选手和高级软件工程师需要掌握的一项重要思维。它不仅仅用于解算法题在解决一些实际的资源调度、电路设计、排班优化等问题时只要规模适中这种思想就能派上用场。最后多练习是关键从经典的TSP、棋盘覆盖开始尝试解决LeetCode或各大OJ上的状态压缩DP专题你会逐渐习惯这种“二进制思考”的模式并感受到它带来的效率飞跃。