1. 从两道经典题看状压DP的核心思想状压DP这个知识点很多人在刚接触动态规划的时候会觉得它神秘又难啃。我第一次遇到蒙德里安的梦想这道题的时候盯着题目看了半小时完全不知道从哪下手。后来才慢慢理解状压DP本质上就是把集合这个抽象概念用一个整数的二进制位来表示从而让状态可以被枚举、被转移。为什么叫状压就是把状态压缩成一个整数。比如有5个物品每个物品选或不选一共2的5次方等于32种状态用0到31的整数就能全部表示。第i位是1就代表选了第i个物品是0就代表没选。这种表示方法在棋盘覆盖、路径规划、集合划分等问题里特别管用。蒙德里安的梦想和最短Hamilton路径这两道题可以说是状压DP的入门双璧。前者教你如何用状态压缩解决棋盘骨牌覆盖的计数问题后者教你如何在状态中记录当前在哪个点来解决路径最优化问题。两道题合在一起练基本上能把状压DP的两种典型套路都摸清楚。这篇文章我会从这两道题出发把状压DP的底层逻辑、状态设计方法、转移方程推导、代码实现细节、以及我踩过的坑全部拆开讲。不管你是刚学DP的新手还是想复习状压DP的老手应该都能从中找到有用的东西。2. 状压DP的底层逻辑与状态设计方法论2.1 为什么需要状压普通DP的局限性普通的线性DP状态通常是一维或二维的比如dp[i]表示前i个元素的最优解dp[i][j]表示前i个元素在某种约束下的最优解。但有些问题里元素之间没有天然的线性顺序或者说选了哪些元素这件事本身就构成了状态的一部分。举个例子在一个N个点的图里从起点出发经过所有点恰好一次求最短路径。如果你用dp[i]表示走到第i个点的最短距离那完全不够——因为你不知道前面已经走过了哪些点而哪些点已经走过直接影响你下一步能走哪里。这时候就需要把已走过的点集也编码进状态里这就是状压DP的动机。用二进制位来表示集合有一个天然优势位运算非常快。判断某个元素是否在集合里用与运算把某个元素加入集合用或运算枚举集合的所有子集用减一与自身的技巧。这些操作在C里都是常数时间比用数组或哈希表表示集合高效得多。2.2 状态压缩的常见表示方式状态压缩最常用的载体是整数的二进制表示。假设有一个大小为N的集合我们用0到2^N - 1的整数来表示它的所有子集。整数x的第i位从0开始计数为1表示第i个元素在集合中。这里有一个细节需要注意位的编号方向。有的人习惯从低位到高位对应元素0到N-1有的人反过来。我建议统一用低位对应小编号这样在写代码的时候不容易搞混。比如N3时二进制101表示选了元素0和元素2对应的十进制是5。除了二进制偶尔也会用到三进制状态压缩比如某些问题里每个元素有三种状态未选、选A、选B。但三进制没法直接用位运算需要手动拆位写起来麻烦很多。绝大多数状压DP题目用二进制就够了。2.3 状压DP的适用条件判断不是所有问题都适合状压DP。判断一个题能不能用状压我一般看三个条件第一问题的规模要小。因为状态数是2的N次方N一般不超过20最好不超过16。N20时状态数是一百多万再乘上转移的复杂度很容易超时。N25基本就别想了。第二问题需要记录集合信息。如果状态只跟位置、数量有关跟选了哪些无关那就不需要状压。第三状态之间的转移可以用位运算高效表达。如果转移涉及复杂的集合操作位运算帮不上忙那状压的优势就不明显。蒙德里安的梦想里N和M最大是11状态数是2的11次方等于2048完全在可控范围内。最短Hamilton路径里N最大是20状态数是2的20次方约一百万需要配合优化才能过。3. 蒙德里安的梦想棋盘覆盖的计数问题3.1 题目核心需求解析蒙德里安的梦想这道题是这样的给定一个N行M列的棋盘用1x2的长方形骨牌去完全覆盖它问有多少种不同的覆盖方案。骨牌可以横着放也可以竖着放但必须恰好覆盖所有格子不能重叠也不能留空。这道题为什么叫蒙德里安的梦想因为荷兰画家蒙德里安的作品里经常出现由矩形色块组成的网格图案这道题的骨牌覆盖方案在视觉上跟他的画风有点像。当然这只是个名字不影响解题。题目的核心难点在于骨牌的摆放方式互相制约。你在这个位置横着放一块旁边两个格子就被占了别的地方就不能再放。这种局部决策影响全局的特性正是状压DP擅长处理的。3.2 按列递推的状态设计思路这道题的经典做法是按列递推用状态表示当前列的突出情况。具体来说我们一列一列地填对于第i列用一个二进制数表示这一列哪些行是被上一列横着放过来的骨牌占用了。为什么按列而不是按行因为骨牌的宽度是2按列处理的时候横着放的骨牌会跨越两列竖着放的骨牌只在一列内。按列递推可以自然地处理横放骨牌的跨列问题。状态定义dp[i][j]表示前i-1列已经填满且第i列的状态为j的方案数。这里的j是一个M位的二进制数第k位为1表示第i列的第k行被第i-1列横着放过来的骨牌占用了也就是说这个格子已经有骨牌了不能再放别的。转移的时候我们枚举第i列的状态j和第i1列的状态k判断从j能否转移到k。判断的条件有两个第一j和k不能在同一行同时为1因为那意味着同一个格子被两块骨牌占用第二j和k合并之后第i列中空出来的连续格子既没有被j占用也没有被k占用的格子必须能用竖着的骨牌填满也就是说连续空格的个数必须是偶数。3.3 状态合法性预处理的技巧直接枚举j和k然后判断合法性复杂度是O(2^M * 2^M * M)当M11时大约是2048204811约四千六百万勉强能过但不够优雅。更常见的做法是预处理出所有合法状态也就是那些自身连续空格为偶数的状态然后在合法状态之间转移。预处理的逻辑是这样的对于一个状态x如果它的二进制表示中连续的0的个数都是偶数那它就是合法的。为什么因为连续的0代表这一列中那些没有被上一列占用的格子它们必须用竖着的骨牌填满而竖骨牌占两个格子所以连续0的个数必须是偶数。我一般用一个数组st[x]来标记状态x是否合法预处理的时候从0到2^M - 1遍历对每个状态检查连续0的个数。检查的方法可以用一个变量cnt记录当前连续0的个数遇到1就检查cnt是否为偶数然后重置cnt。bool st[1 11]; for (int i 0; i (1 M); i) { int cnt 0; bool valid true; for (int j 0; j M; j) { if ((i j) 1) { if (cnt 1) { valid false; break; } cnt 0; } else { cnt; } } if (cnt 1) valid false; st[i] valid; }这段代码里cnt 1用来判断cnt是否为奇数比cnt % 2 1更快。最后还要再检查一次cnt因为状态末尾可能是一串0。3.4 转移方程与边界条件有了合法性预处理转移就清晰了。对于第i列的状态j和第i1列的状态k如果(j k) 0且st[j | k]为真那就可以从dp[i][j]转移到dp[i1][k]。边界条件是dp[0][0] 1表示第0列没有任何突出方案数为1。最终答案是dp[M][0]表示第M列最后一列的下一列没有任何突出也就是所有列都填满了。这里有一个容易搞混的地方dp数组的第二维大小是2^M第一维大小是M1。因为我们要处理到第M列而第M列的状态必须是0没有突出到棋盘外面。dp[0][0] 1; for (int i 0; i M; i) { for (int j 0; j (1 N); j) { if (dp[i][j] 0) continue; for (int k 0; k (1 N); k) { if ((j k) 0 st[j | k]) { dp[i 1][k] dp[i][j]; } } } }注意这里N和M的角色N是行数M是列数。状态的大小是2^N因为状态表示的是每一行的情况。我见过不少人把N和M搞反导致状态数组开小了或者循环写错了。3.5 实操中的坑与优化建议第一个坑是N和M的顺序。题目里N是行数M是列数但状态压缩的是行方向所以状态大小是2^N。如果N比M大很多比如N11M1那状态数就是2048但列数只有1循环次数很少。反过来如果N1M11状态数只有2但列数有11。两种情况下复杂度都不高但如果N11M11那就是2048204811约四千六百万次操作需要用long long存答案因为方案数可能很大。第二个坑是dp数组的初始化。每次多组测试数据的时候一定要把dp数组清零。我一般用memset或者循环清零但要注意dp数组的大小是(M1) * (1N)别清多了也别清少了。第三个坑是状态合法性预处理的边界。当M0或者N0的时候题目一般不会给这种数据但保险起见可以特判一下。优化方面如果时间卡得紧可以把合法状态单独存到一个数组里转移的时候只遍历合法状态能省不少时间。另外如果dp[i][j]为0直接continue跳过无效状态。4. 最短Hamilton路径状态中记录当前位置4.1 问题建模与状态定义最短Hamilton路径问题是这样的给定一个N个点的带权无向图从点0出发经过每个点恰好一次最后到达点N-1求路径总权值的最小值。Hamilton路径就是经过所有点恰好一次的路径这个问题是NP难的但因为N很小一般不超过20可以用状压DP在O(2^N * N^2)的时间内解决。状态定义dp[i][j]表示当前已经走过的点集为i且最后停在点j的最小路径长度。这里的i是一个N位的二进制数第k位为1表示点k已经走过。为什么要在状态里记录最后停在哪个点因为路径的权值跟相邻两点有关如果你不知道上一步在哪里就没法计算下一步的权值。所以状态必须包含当前位置信息。4.2 状态转移的推导过程转移的时候我们枚举当前状态i和当前位置j然后枚举下一个要去的点k。如果k不在i中即i的第k位为0那就可以从dp[i][j]转移到dp[i | (1k)][k]转移的代价是g[j][k]也就是从j到k的边权。转移方程dp[i | (1k)][k] min(dp[i | (1k)][k], dp[i][j] g[j][k])。初始条件是dp[1][0] 0表示只走了点0当前在点0路径长度为0。最终答案是dp[(1N) - 1][N-1]表示所有点都走过了最后停在点N-1。这里有一个细节为什么初始状态是dp[1][0]而不是dp[0][0]因为点0是起点必须已经走过所以状态i的第0位必须是1。如果写成dp[0][0]那表示一个点都没走但当前位置是0这自相矛盾。memset(dp, 0x3f, sizeof(dp)); dp[1][0] 0; for (int i 1; i (1 N); i) { for (int j 0; j N; j) { if (!(i j 1)) continue; if (dp[i][j] INF) continue; for (int k 0; k N; k) { if (i k 1) continue; dp[i | (1 k)][k] min(dp[i | (1 k)][k], dp[i][j] g[j][k]); } } }这段代码里0x3f3f3f3f是常用的无穷大表示它的两倍不会溢出int。i j 1用来判断点j是否在集合i中注意运算符优先级比高所以要先移位再与。4.3 枚举顺序与边界处理枚举顺序很重要。外层循环枚举状态i从1到2^N - 1。内层循环枚举当前位置j再内层枚举下一个点k。为什么状态要从小到大枚举因为转移是从小状态到大状态i | (1k)一定大于i所以按i从小到大枚举能保证转移时用到的dp值已经计算好了。边界处理方面如果图不连通那答案就是无穷大但题目一般保证有解。另外如果N1那答案就是0因为起点就是终点。这种情况可以特判也可以让代码自然处理——dp[1][0] 0最终答案是dp[1][0] 0正好对。还有一个容易忽略的点dp数组的初始化。因为要求最小值所以dp数组要初始化为无穷大只有dp[1][0]初始化为0。我见过有人把dp数组全部初始化为0结果答案永远是0因为min操作取到了0。4.4 与蒙德里安梦想的对比分析这两道题虽然都是状压DP但状态设计和转移方式有明显区别。蒙德里安的梦想是按列递推状态表示的是当前列的突出情况转移是列与列之间的转移。状态的大小是2^NN是行数但状态本身不包含当前位置信息因为位置由外层循环的列号隐含了。最短Hamilton路径是按点集递推状态表示的是已走过的点集和当前位置转移是点与点之间的转移。状态的大小是2^N * N因为要额外记录当前位置。从复杂度上看蒙德里安是O(M * 2^N * 2^N)Hamilton是O(2^N * N^2)。蒙德里安的复杂度对N更敏感Hamilton对N的敏感度稍低一些。从状态合法性上看蒙德里安需要预处理合法状态因为不是所有状态都能填满Hamilton不需要预处理因为所有状态都是合法的只要点集和当前位置一致。我个人的体会是蒙德里安的难点在于状态合法性的判断和转移条件的推导Hamilton的难点在于状态维度的设计和枚举顺序的安排。两道题练完基本上能把状压DP的常见套路都覆盖到。5. 状压DP的通用优化技巧与实战经验5.1 位运算的常见操作与陷阱状压DP里位运算用得非常频繁这里整理几个常用的操作和容易踩的坑。判断第i位是否为1(x i) 1。注意不要写成x (1 i)然后直接当布尔值用虽然结果非零就是真但类型是int在某些编译器上可能有警告。把第i位置为1x | (1 i)。把第i位置为0x ~(1 i)。翻转第i位x ^ (1 i)。枚举x的所有子集for (int sub x; sub; sub (sub - 1) x)。这个技巧在子集DP里非常有用注意循环条件是sub非零因为空集一般不需要单独处理。判断x是否是2的幂x (x - 1)等于0。这个操作常用来判断一个集合是否只有一个元素。一个常见的坑是运算符优先级。的优先级比低所以if (x 1 1)实际上等价于if (x (1 1))也就是if (x 1)虽然结果碰巧对但逻辑是错的。正确的写法是if ((x 1) 1)。另一个坑是移位操作的位数。1 31在int下是未定义行为因为1是int左移31位会溢出。如果要表示第31位应该用1LL 31。在状压DP里N一般不超过20所以这个问题不常见但养成好习惯没坏处。5.2 滚动数组与空间优化当状态的第一维很大时比如蒙德里安的梦想里M可能很大但dp[i]只依赖于dp[i-1]这时候可以用滚动数组把空间从O(M * 2^N)降到O(2^N)。滚动数组的写法是用两个数组交替或者用i 1作为下标。比如dp[0][0] 1; for (int i 0; i M; i) { memset(dp[(i 1) 1], 0, sizeof(dp[0])); for (int j 0; j (1 N); j) { if (dp[i 1][j] 0) continue; for (int k 0; k (1 N); k) { if ((j k) 0 st[j | k]) { dp[(i 1) 1][k] dp[i 1][j]; } } } }注意每次进入新的一轮之前要把下一轮的数组清零。这个细节很容易忘忘了的话上一轮的数据会残留导致答案错误。Hamilton路径问题里dp[i][j]的第一维是状态第二维是位置空间是2^N * N。当N20时2^20 * 20约两千万个int大约80MB有点大但还能接受。如果内存限制紧可以考虑用short或者把状态按位数分组但一般没必要。5.3 时间复杂度的估算与剪枝状压DP的时间复杂度通常是O(2^N * N)或O(2^N * N^2)或O(2^N * 2^N)。估算的时候要注意常数因子。以Hamilton路径为例外层2^N内层N再内层N总共2^N * N^2。N20时是1,048,576 * 400约四亿次操作。这个量级在C里大概需要1到2秒如果时间限制是1秒可能过不了。这时候需要剪枝。剪枝的方法有几种第一如果dp[i][j]是无穷大直接continue跳过无效状态。第二如果当前状态i中1的个数小于某个值可以跳过但Hamilton路径里所有状态都可能有效这个剪枝不适用。第三把内层循环的k限制在未访问的点里可以用位运算快速找到未访问的点。我实测下来加了第一个剪枝之后Hamilton路径在N20时大概能跑到0.5秒左右基本够用。如果还不行可以考虑用更快的输入输出或者把g数组改成一维数组提高缓存命中率。5.4 常见错误类型与调试方法状压DP的常见错误我归纳为四类第一类是状态定义错误。比如Hamilton路径里忘了记录当前位置或者蒙德里安里状态的含义搞反了。这类错误的表现是答案完全不对或者样例都过不了。调试方法是手动模拟小数据把dp数组打印出来看。第二类是边界条件错误。比如dp数组初始化不对或者最终答案取错了位置。这类错误的表现是答案差一点或者某些特殊情况不对。调试方法是构造边界数据比如N1、M1的情况。第三类是位运算错误。比如运算符优先级搞错或者移位位数超了。这类错误比较隐蔽因为有时候碰巧结果对。调试方法是把位运算单独拿出来测试确认每个操作的结果符合预期。第四类是数组越界。比如状态数组开小了或者循环变量超了范围。这类错误可能导致程序崩溃或者结果随机。调试方法是把数组开大一点看看结果是否变化。我一般用一个小技巧来调试状压DP把状态i用二进制打印出来同时打印dp[i][j]的值这样能直观地看到状态的转移过程。对于小数据N4这个方法非常有效。6. 从两道题延伸到状压DP的更多应用场景6.1 旅行商问题与Hamilton路径的关系旅行商问题TSP是Hamilton路径的变体从起点出发经过所有点恰好一次最后回到起点求最短路径。TSP的状压DP做法跟Hamilton路径几乎一样只是最终答案不是dp[(1N)-1][N-1]而是min(dp[(1N)-1][j] g[j][0])也就是回到起点的代价。TSP的经典解法就是状压DP复杂度O(2^N * N^2)。当N20时跟Hamilton路径一样需要优化。TSP在实际中有很多应用比如物流配送路线规划、电路板钻孔路径优化等。当然实际问题的规模远大于20需要用近似算法或启发式算法但状压DP是理解这些算法的基础。6.2 棋盘覆盖类问题的通用套路蒙德里安的梦想是棋盘覆盖类问题的代表。这类问题的通用套路是按行或按列递推用状态表示突出或占用情况预处理合法状态然后枚举状态转移。类似的题目有用L形骨牌覆盖棋盘、用1x3骨牌覆盖棋盘、在棋盘上放国王相邻格子不能同时放、在棋盘上放炮兵攻击范围不同等。这些题的状态设计和转移条件各不相同但整体框架是一样的。我做这类题的经验是先确定按行还是按列递推然后确定状态表示什么再推导转移条件最后预处理合法状态。这四步走下来大部分棋盘覆盖类问题都能解决。6.3 集合划分与子集枚举DP除了路径和棋盘状压DP还常用于集合划分问题。比如把N个元素分成若干组每组满足某种条件求方案数或最优解。这类问题的状态通常表示已经划分了哪些元素转移是枚举当前组的子集。子集枚举DP的经典题目是分成若干组使每组和相等或分成若干组使组内元素满足某种关系。这类问题的复杂度通常是O(3^N)因为要枚举所有子集。3^N (2^N)^(log2(3))约等于2^(1.585N)当N15时约一千四百万还能接受。枚举子集的技巧是for (int sub x; sub; sub (sub - 1) x)这个循环会枚举x的所有非空子集。如果要包含空集可以在循环外面单独处理。6.4 状压DP与其他算法的结合状压DP经常和其他算法结合使用。比如状压DP BFS用于解决状态空间搜索问题状压DP 矩阵快速幂用于解决状态转移有规律且需要大量重复的问题状压DP 容斥原理用于解决计数问题。我印象比较深的是一个用骨牌覆盖棋盘且骨牌有颜色的问题状态里不仅要记录覆盖情况还要记录颜色信息状态数直接翻倍。这种时候就需要仔细设计状态把能合并的信息合并减少状态数。另一个常见的结合是状压DP 记忆化搜索。有些问题的状态转移不是按顺序的用递推不好写用记忆化搜索更自然。比如在棋盘上放棋子棋子之间有条件约束的问题用记忆化搜索写起来比递推清晰。7. 我的实战心得与避坑清单7.1 状态设计的三个原则做了这么多状压DP的题我总结出状态设计的三个原则第一状态要能唯一确定后续决策所需的信息。如果两个不同的状态对后续决策的影响是一样的那它们应该被合并。比如Hamilton路径里如果两个状态的已走点集相同、当前位置相同那后续的最优解只取决于这两个信息跟路径的具体走法无关。第二状态数要尽量少。状态数直接决定复杂度所以能省则省。比如蒙德里安里合法状态只有那些连续0为偶数的状态预处理之后状态数减少了很多。第三状态转移要能用位运算高效表达。如果转移涉及复杂的集合操作位运算帮不上忙那状压的优势就不明显可能需要换一种思路。7.2 调试状压DP的实用技巧调试状压DP的时候我一般用这几个技巧第一从小数据开始。N2或N3的时候手动枚举所有情况算出正确答案然后跟程序输出对比。如果不对把dp数组打印出来看哪一步转移错了。第二把状态用二进制打印。比如printf(dp[%d][%d] %d\n, i, j, dp[i][j])同时把i用二进制打印出来这样能直观地看到状态的转移。第三检查边界条件。dp数组的初始化、最终答案的取值、循环的起止范围这些地方最容易出错。第四用对拍。写一个暴力程序随机生成小数据跟状压DP程序对比。这个方法虽然麻烦但最可靠。7.3 常见问题速查表问题现象可能原因排查方法样例都过不了状态定义错误手动模拟小数据打印dp数组答案差一点边界条件错误检查dp初始化和最终答案取值答案随机变化数组越界把数组开大看结果是否变化程序超时复杂度太高加剪枝用滚动数组优化位运算答案溢出没用long long把dp数组改成long long多组数据答案错误没清零每组数据前memset dp数组7.4 从新手到熟练的练习路径如果你刚学状压DP我建议按这个顺序练习先做蒙德里安的梦想理解状态压缩的基本思想和按列递推的套路。然后做最短Hamilton路径理解状态中记录位置的必要性和枚举顺序的安排。接着做炮兵阵地或国王这类棋盘放置问题练习状态合法性判断和转移条件推导。最后做集合划分类问题练习子集枚举和3^N复杂度的处理。每道题做完之后不要只看答案对不对还要看代码是否简洁、是否有优化空间、是否能举一反三。我一般会把同一类题的代码放在一起对比找出共性和差异这样进步最快。状压DP这个知识点入门的时候觉得难但做多了之后会发现套路很固定。关键是理解状态设计的逻辑掌握位运算的技巧然后多练多总结。蒙德里安的梦想和最短Hamilton路径这两道题我前前后后做了不下十遍每次都有新的体会。希望你也能从中找到乐趣。