状压DP入门：从蒙德里安到Hamilton路径的实战解析

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，有的人反过来。我建议统一用低位对应小编号，这样在写代码的时候不容易搞混。比如N=3时，二进制101表示选了元素0和元素2，对应的十进制是5。

除了二进制，偶尔也会用到三进制状态压缩，比如某些问题里每个元素有三种状态（未选、选A、选B）。但三进制没法直接用位运算，需要手动拆位，写起来麻烦很多。绝大多数状压DP题目用二进制就够了。

2.3 状压DP的适用条件判断

不是所有问题都适合状压DP。判断一个题能不能用状压，我一般看三个条件：

第一，问题的规模要小。因为状态数是2的N次方，N一般不超过20，最好不超过16。N=20时状态数是一百多万，再乘上转移的复杂度，很容易超时。N=25基本就别想了。

第二，问题需要记录"集合"信息。如果状态只跟位置、数量有关，跟"选了哪些"无关，那就不需要状压。

第三，状态之间的转移可以用位运算高效表达。如果转移涉及复杂的集合操作，位运算帮不上忙，那状压的优势就不明显。

"蒙德里安的梦想"里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和第i+1列的状态k，判断从j能否转移到k。判断的条件有两个：第一，j和k不能在同一行同时为1，因为那意味着同一个格子被两块骨牌占用；第二，j和k合并之后，第i列中空出来的连续格子（既没有被j占用也没有被k占用的格子）必须能用竖着的骨牌填满，也就是说连续空格的个数必须是偶数。

3.3 状态合法性预处理的技巧

直接枚举j和k然后判断合法性，复杂度是O(2^M * 2^M * M)，当M=11时大约是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和第i+1列的状态k，如果(j & k) == 0且st[j | k]为真，那就可以从dp[i][j]转移到dp[i+1][k]。

边界条件是dp[0][0] = 1，表示第0列没有任何突出，方案数为1。最终答案是dp[M][0]，表示第M列（最后一列的下一列）没有任何突出，也就是所有列都填满了。

这里有一个容易搞混的地方：dp数组的第二维大小是2^M，第一维大小是M+1。因为我们要处理到第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大很多，比如N=11，M=1，那状态数就是2048，但列数只有1，循环次数很少。反过来如果N=1，M=11，状态数只有2，但列数有11。两种情况下复杂度都不高，但如果N=11，M=11，那就是2048204811约四千六百万次操作，需要用long long存答案，因为方案数可能很大。

第二个坑是dp数组的初始化。每次多组测试数据的时候，一定要把dp数组清零。我一般用memset或者循环清零，但要注意dp数组的大小是(M+1) * (1<<N)，别清多了也别清少了。

第三个坑是状态合法性预处理的边界。当M=0或者N=0的时候，题目一般不会给这种数据，但保险起见可以特判一下。

优化方面，如果时间卡得紧，可以把合法状态单独存到一个数组里，转移的时候只遍历合法状态，能省不少时间。另外，如果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 | (1<<k)][k]，转移的代价是g[j][k]，也就是从j到k的边权。

转移方程：dp[i | (1<<k)][k] = min(dp[i | (1<<k)][k], dp[i][j] + g[j][k])。

初始条件是dp[1][0] = 0，表示只走了点0，当前在点0，路径长度为0。最终答案是dp[(1<<N) - 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 | (1<<k)一定大于i），所以按i从小到大枚举能保证转移时用到的dp值已经计算好了。

边界处理方面，如果图不连通，那答案就是无穷大，但题目一般保证有解。另外，如果N=1，那答案就是0，因为起点就是终点。这种情况可以特判，也可以让代码自然处理——dp[1][0] = 0，最终答案是dp[1][0] = 0，正好对。

还有一个容易忽略的点：dp数组的初始化。因为要求最小值，所以dp数组要初始化为无穷大，只有dp[1][0]初始化为0。我见过有人把dp数组全部初始化为0，结果答案永远是0，因为min操作取到了0。

4.4 与蒙德里安梦想的对比分析

这两道题虽然都是状压DP，但状态设计和转移方式有明显区别。

蒙德里安的梦想是"按列递推"，状态表示的是"当前列的突出情况"，转移是列与列之间的转移。状态的大小是2^N（N是行数），但状态本身不包含"当前位置"信息，因为位置由外层循环的列号隐含了。

最短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位置为1：x | (1 << i)。把第i位置为0：x & ~(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。当N=20时，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。N=20时是1,048,576 * 400约四亿次操作。这个量级在C++里大概需要1到2秒，如果时间限制是1秒，可能过不了。这时候需要剪枝。

剪枝的方法有几种：第一，如果dp[i][j]是无穷大，直接continue，跳过无效状态。第二，如果当前状态i中1的个数小于某个值，可以跳过，但Hamilton路径里所有状态都可能有效，这个剪枝不适用。第三，把内层循环的k限制在未访问的点里，可以用位运算快速找到未访问的点。

我实测下来，加了第一个剪枝之后，Hamilton路径在N=20时大概能跑到0.5秒左右，基本够用。如果还不行，可以考虑用更快的输入输出，或者把g数组改成一维数组提高缓存命中率。

5.4 常见错误类型与调试方法

状压DP的常见错误我归纳为四类：

第一类是状态定义错误。比如Hamilton路径里忘了记录当前位置，或者蒙德里安里状态的含义搞反了。这类错误的表现是答案完全不对，或者样例都过不了。调试方法是手动模拟小数据，把dp数组打印出来看。

第二类是边界条件错误。比如dp数组初始化不对，或者最终答案取错了位置。这类错误的表现是答案差一点，或者某些特殊情况不对。调试方法是构造边界数据，比如N=1、M=1的情况。

第三类是位运算错误。比如运算符优先级搞错，或者移位位数超了。这类错误比较隐蔽，因为有时候碰巧结果对。调试方法是把位运算单独拿出来测试，确认每个操作的结果符合预期。

第四类是数组越界。比如状态数组开小了，或者循环变量超了范围。这类错误可能导致程序崩溃或者结果随机。调试方法是把数组开大一点，看看结果是否变化。

我一般用一个小技巧来调试状压DP：把状态i用二进制打印出来，同时打印dp[i][j]的值，这样能直观地看到状态的转移过程。对于小数据（N<=4），这个方法非常有效。

6. 从两道题延伸到状压DP的更多应用场景

6.1 旅行商问题与Hamilton路径的关系

旅行商问题（TSP）是Hamilton路径的变体：从起点出发，经过所有点恰好一次，最后回到起点，求最短路径。TSP的状压DP做法跟Hamilton路径几乎一样，只是最终答案不是dp[(1<<N)-1][N-1]，而是min(dp[(1<<N)-1][j] + g[j][0])，也就是回到起点的代价。

TSP的经典解法就是状压DP，复杂度O(2^N * N^2)。当N=20时，跟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)，当N=15时约一千四百万，还能接受。

枚举子集的技巧是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的时候，我一般用这几个技巧：

第一，从小数据开始。N=2或N=3的时候，手动枚举所有情况，算出正确答案，然后跟程序输出对比。如果不对，把dp数组打印出来，看哪一步转移错了。

第二，把状态用二进制打印。比如printf("dp[%d][%d] = %d\n", i, j, dp[i][j])，同时把i用二进制打印出来，这样能直观地看到状态的转移。

第三，检查边界条件。dp数组的初始化、最终答案的取值、循环的起止范围，这些地方最容易出错。

第四，用对拍。写一个暴力程序，随机生成小数据，跟状压DP程序对比。这个方法虽然麻烦，但最可靠。

7.3 常见问题速查表

7.4 从新手到熟练的练习路径

如果你刚学状压DP，我建议按这个顺序练习：

先做"蒙德里安的梦想"，理解状态压缩的基本思想和按列递推的套路。然后做"最短Hamilton路径"，理解状态中记录位置的必要性和枚举顺序的安排。接着做"炮兵阵地"或"国王"这类棋盘放置问题，练习状态合法性判断和转移条件推导。最后做"集合划分"类问题，练习子集枚举和3^N复杂度的处理。

每道题做完之后，不要只看答案对不对，还要看代码是否简洁、是否有优化空间、是否能举一反三。我一般会把同一类题的代码放在一起对比，找出共性和差异，这样进步最快。

状压DP这个知识点，入门的时候觉得难，但做多了之后会发现套路很固定。关键是理解状态设计的逻辑，掌握位运算的技巧，然后多练多总结。蒙德里安的梦想和最短Hamilton路径这两道题，我前前后后做了不下十遍，每次都有新的体会。希望你也能从中找到乐趣。