企业官网建设流程全解析

1. 从两道题看懂状压DP到底在压什么

状压DP这个名词，刚接触算法竞赛的人多半会被"状压"两个字唬住，以为是什么高深的压缩算法。其实说白了，它就是把一个集合的状态用一个整数的二进制位来表示，然后在这个"压缩后的状态"上做动态规划。我第一次学的时候也绕了很久，直到把蒙德里安的梦想这道题手推了一遍，才真正理解为什么要把状态压进一个int里。

先说说为什么需要状压。普通的动态规划，状态通常是一个或几个整数，比如背包问题里的容量、最长上升子序列里的位置。但有些问题，状态本身就是一个集合——比如"哪些位置已经被访问过了""哪些格子已经被填充了"。如果直接用布尔数组存集合，状态数量会爆炸，而且没法作为DP数组的下标。这时候二进制就派上用场了：一个长度为n的二进制数，第i位是0还是1，就代表第i个元素在不在集合里。n个元素的集合，总共2的n次方种状态，全部能塞进一个整数。

这个思路的妙处在于，整数的位运算天然适合描述集合操作。判断第i位是否为1用(state >> i) & 1，把第i位置1用state | (1 << i)，两个集合求并集用|，求交集用&。这些操作都是O(1)的，比操作数组快得多。所以状压DP本质上是一种"用位运算加速集合状态转移"的技巧，核心适用条件是：状态可以用一个不大的集合描述，且集合大小n通常在20以内（2的20次方约一百万，再大内存和时间都扛不住）。

蒙德里安的梦想和最短Hamilton路径这两道题，恰好是状压DP的两个经典入门方向。前者是"棋盘填充类"，状态表示某一行的填充情况，转移时考虑相邻两行的兼容性；后者是"路径规划类"，状态表示已经访问过的点集以及当前停在哪个点。两道题放在一起练，能把状压DP的两大主流套路都摸清楚。下面我按自己的理解顺序，把这两道题从建模到实现完整拆一遍，中间会穿插一些我踩过的坑和调试技巧。

2. 蒙德里安的梦想：骨牌铺满棋盘的计数问题

2.1 题目本质与状态定义的关键抉择

蒙德里安的梦想原题大意是：给定一个N行M列的棋盘，用1×2的长方形骨牌（可以横放也可以竖放）把它完全铺满，问有多少种不同的铺法。N和M通常一个很小（比如N≤11），另一个可以稍大。这道题看起来是个组合计数问题，但直接枚举所有铺法会超时，必须用DP。

关键在于怎么定义状态。一个很自然的想法是逐行填充：假设我们从上往下一行一行地铺，那么铺到第i行时，第i行的填充情况会受到第i-1行竖着伸下来的骨牌的影响。具体来说，如果第i-1行某个位置竖放了一块骨牌，那它就会占据第i行的同一个位置，这个位置在第i行就不能再放别的东西了。

所以状态可以定义为：dp[i][state]表示铺完前i-1行、且第i行的"被占用情况"为state时的方案数。这里的state是一个M位的二进制数，第j位为1表示第i行的第j列已经被上一行竖放的骨牌占用了，为0表示还空着。注意这个定义里，state描述的是"当前行哪些位置被上一行影响"，而不是"当前行已经铺了什么"。

我第一次做这道题时，最大的困惑是：为什么状态要定义成"被上一行占用"而不是"当前行已填充"？后来想明白了，因为DP是逐行推进的，当前行的填充方案其实是在转移过程中确定的，我们只需要记录"上一行留给当前行的约束"就够了。这个约束就是哪些位置被竖牌占了。这种"记录前一行对当前行的影响"的思路，在棋盘类状压DP里非常常见。

2.2 合法状态预处理：为什么有些state根本不可能出现

不是所有的state都是合法的。考虑一个M位的state，它表示当前行哪些位置被上一行的竖牌占用。那么当前行剩下的空位（state为0的位置）必须能用横放的骨牌填满，因为竖牌的位置已经被占了，不能再放。而横放骨牌是1×2的，所以空位必须能两两配对，也就是说，state中连续的0的个数必须是偶数。

举个例子，M=4，state=0101（从低位到高位，第0位是1，第1位是0，第2位是1，第3位是0）。空位是第1位和第3位，它们不连续，各自单独一个0，没法用横牌填满，所以这个state不合法。再比如state=1001，空位是第1、2位，连续两个0，可以用一块横牌填满，合法。

所以第一步是预处理出所有合法的state。判断方法很简单：从低位到高位扫描，遇到0就计数，遇到1就检查之前累计的0的个数是否为偶数，不是就非法；扫完后还要检查最后一段0的个数是否为偶数。这个预处理是O(2^M * M)的，M≤11时完全没问题。

bool check(int state, int m) { int cnt = 0; for (int j = 0; j < m; j++) { if ((state >> j) & 1) { if (cnt & 1) return false; cnt = 0; } else { cnt++; } } return (cnt & 1) == 0; }

这段代码我建议背下来，棋盘类状压DP里判断"连续空位是否为偶数"是高频操作。注意最后那个(cnt & 1) == 0不能漏，我见过不少人只检查了遇到1时的情况，忘了收尾。

2.3 状态转移：两行之间如何衔接

预处理完合法状态后，转移方程就好写了。dp[i][state]表示第i行的占用情况为state时的方案数。那么它可以从第i-1行的某个状态prev转移过来，前提是prev和state兼容。

什么叫兼容？第i-1行的状态prev表示第i-1行被第i-2行占用的位置。第i-1行在铺的时候，会在prev为0的位置上放横牌或竖牌。如果放竖牌，就会占用第i行的对应位置，这些位置在state里必须是1。如果放横牌，会占用第i-1行相邻两个位置，不影响第i行。

所以兼容条件有两个：第一，prev和state不能有重叠的1，因为第i-1行被上一行占的位置，不可能同时又被第i-1行自己竖放的牌占用。也就是(prev & state) == 0。第二，prev | state这个合并后的状态，其空位（即两个都是0的位置）必须能用横牌填满，也就是prev | state必须是合法状态。

等等，这里有个细节容易搞混。prev | state表示的是第i-1行"被占用"的所有位置——包括被第i-2行竖牌占的（prev的1）和被第i-1行自己竖牌占的（state的1）。这些位置都不能放横牌，剩下的空位要放横牌，所以空位必须连续偶数。这正是prev | state合法的含义。

转移方程就是：对于每个合法的state，遍历所有合法的prev，如果(prev & state) == 0且check(prev | state)为真，就累加。

for (int i = 1; i <= n; i++) { for (int state : validStates) { for (int prev : validStates) { if ((prev & state) == 0 && check(prev | state, m)) { dp[i][state] += dp[i-1][prev]; } } } }

最终答案是dp[n+1][0]，意思是铺完前n行后，第n+1行没有任何被占用的位置。这个技巧很常用：多开一行，答案落在"下一行完全空"的状态上，避免了单独处理最后一行的边界。

2.4 复杂度优化与滚动数组的实战取舍

上面这个三重循环，复杂度是O(N * 2^M * 2^M)，当M=11时，2^M=2048，两层就是约四百万，再乘N（假设N=11）就是四千多万，勉强能过但有点悬。实际写的时候有两个优化方向。

第一个是预处理兼容关系。因为state和prev的兼容性只跟它们本身有关，跟行号i无关，所以可以预先算出一个邻接表，记录每个state能由哪些prev转移过来。这样内层循环只遍历真正兼容的prev，能砍掉大量无效判断。实测下来，合法状态本身就不多（M=11时大概几百个），兼容对更少，速度提升很明显。

第二个是滚动数组。dp[i]只依赖dp[i-1]，所以完全可以用两个一维数组交替，把空间从O(N * 2^M)降到O(2^M)。不过这道题N和M都不大，空间不是瓶颈，滚动数组更多是习惯问题。我个人的建议是：如果题目空间限制紧，或者N很大，就上滚动数组；否则写二维更直观，调试也方便。

提示：预处理兼容关系时，注意用vector存邻接表，不要用二维bool数组，因为合法状态是稀疏的，用vector遍历更快。

还有一个坑：答案可能很大，要用long long。我见过有人用int结果溢出，调了半天以为是转移写错了。棋盘填充的方案数增长很快，N和M稍微大一点就爆int了。

3. 最短Hamilton路径：路径规划类状压DP的套路

3.1 从旅行商问题说起：状态为什么必须包含"当前在哪"

最短Hamilton路径问题是：给定一张n个点的带权无向图，求从起点0到终点n-1、经过每个点恰好一次的最短路径长度。这就是经典的旅行商问题（TSP）的变体，只不过起点和终点固定了。

如果不用状压，这题只能暴力枚举所有排列，复杂度O(n!)，n=20时完全不可行。用状压DP，复杂度降到O(2^n * n^2)，n=20时约四亿，虽然也不小，但配合优化能过。

状态定义是这道题的核心：dp[state][i]表示已经访问过的点集为state、且当前停在点i时的最短路径长度。这里state是一个n位的二进制数，第j位为1表示点j已经访问过。为什么状态里必须包含"当前停在哪个点"？因为路径长度依赖于你从哪个点走到下一个点，如果只知道访问了哪些点而不知道当前在哪，就没法计算下一步的代价。这是路径类状压DP和棋盘类的一个重要区别：棋盘类通常不需要记录"当前处理到哪个格子"，而路径类必须记录"当前所在位置"。

初始状态是dp[1][0] = 0，表示只访问了点0、当前在点0，路径长度为0。其他所有状态初始化为无穷大。最终答案是dp[(1<<n)-1][n-1]，即所有点都访问过、当前在终点n-1的最短路径。

3.2 转移的枚举顺序：为什么外层枚举state、内层枚举i

转移方程是：对于每个状态state和当前点i，枚举下一个要去的点j（j不在state里），更新dp[state | (1<<j)][j] = min(dp[state | (1<<j)][j], dp[state][i] + w[i][j])。

这里有个枚举顺序的问题。正确的顺序是外层枚举state，内层枚举i，再内层枚举j。为什么？因为状态转移是从"访问点集较小"到"访问点集较大"的，state | (1<<j)一定大于state（二进制上多了一个1），所以按state从小到大枚举，就能保证转移时用到的dp[state][i]已经被计算过了。如果外层枚举i，内层枚举state，就会出现用还没算出来的状态去更新别人的情况，结果错误。

这个顺序问题我踩过坑。当时觉得"先枚举当前点再枚举状态"更符合直觉，结果跑出来答案偏大，查了好久才发现是转移顺序错了。记住一个原则：状压DP里，状态值（二进制数）小的必须先算，因为它可能被大的状态依赖。

memset(dp, 0x3f, sizeof(dp)); dp[1][0] = 0; for (int state = 1; state < (1 << n); state++) { for (int i = 0; i < n; i++) { if (!((state >> i) & 1)) continue; if (dp[state][i] == INF) continue; for (int j = 0; j < n; j++) { if ((state >> j) & 1) continue; int nxt = state | (1 << j); dp[nxt][j] = min(dp[nxt][j], dp[state][i] + w[i][j]); } } }

注意那个if (dp[state][i] == INF) continue;的剪枝，能省不少时间。因为不是所有(state, i)组合都是可达的，比如state里没有i却枚举到i，或者state对应的路径根本不存在。

3.3 边界处理与无穷大的选择

无穷大的选择有讲究。如果用0x3f3f3f3f，两个相加不会溢出int，这是算法竞赛里的常用值。如果用INT_MAX，加边权时会溢出变成负数，导致min取到错误的值。这个坑很隐蔽，因为溢出后结果看起来"变小了"，反而可能被误认为是更优解。

另外，起点和终点的处理也要注意。如果起点和终点是同一个点（n=1的情况），答案应该是0，但代码里dp[1][0]初始为0，最终答案是dp[1][0]，也是0，没问题。但如果题目要求起点和终点不同，就要特判n=1时无解。

还有一个细节：如果图不是完全图，某些点之间没有边，那么w[i][j]要设成无穷大，转移时自然就不会走这条边。但要注意无穷大加无穷大会溢出，所以最好在转移前判断一下w[i][j]是否为无穷大。

3.4 和蒙德里安梦想的对比：两类状压DP的思维差异

把这两道题放一起看，能发现状压DP的两大流派。蒙德里安梦想属于"填充类"，状态描述的是"某个维度的占用情况"，转移时考虑相邻维度的兼容性，不需要记录"当前位置"，因为位置是隐含在DP的推进方向里的。最短Hamilton路径属于"路径类"，状态描述的是"已经访问的集合"，必须额外记录"当前所在位置"，因为路径的代价依赖于位置。

这个差异决定了状态定义的维度。填充类通常是dp[行][状态]，路径类通常是dp[状态][位置]。填充类的状态转移是"整行整行"推进的，路径类是"一个点一个点"推进的。填充类通常需要预处理合法状态，路径类通常不需要（因为任何子集都可能出现）。

理解了这两类，遇到新的状压DP题就能快速归类。比如"用L形骨牌铺棋盘"是填充类，"经过所有城市的最短回路"是路径类，"选出一个子集满足某种性质"是子集类。归类之后，状态定义和转移方式基本就有谱了。

4. 状压DP的通用调试技巧与常见错误

4.1 位运算优先级：那些年我们写错的括号

位运算的优先级是状压DP里最容易出错的地方。在C++里，&、|、^的优先级低于==、!=、<、>，而<<、>>的优先级又高于比较运算符。这意味着state & 1 == 1会被解析成state & (1 == 1)，也就是state & 1，结果完全不对。

我个人的习惯是：只要涉及位运算和比较混用，一律加括号。((state >> i) & 1) == 1这样写虽然啰嗦，但绝对不会错。宁可多打几个括号，也不要花半小时调试一个优先级问题。

还有一个常见的坑是1 << n当n较大时溢出。如果n=31，1 << 31在int下是负数（因为符号位被置1）。所以当n可能达到30以上时，要用1LL << n或者把状态定义成long long。不过状压DP的n通常不超过20，这个问题不常见，但要知道。

4.2 状态合法性检查的遗漏点

填充类状压DP里，状态合法性检查最容易漏的是"收尾检查"。前面提到过，扫描完所有位后，最后一段连续的0也要检查是否为偶数。我见过不少人写的check函数只检查了遇到1时的情况，忘了最后一段，导致一些非法状态被当成合法，答案偏大。

另一个遗漏点是"状态是否可达"。在路径类DP里，不是所有(state, i)组合都对应真实路径。比如state=0b101（访问了点0和点2），但i=1（当前在点1），这是矛盾的，因为点1不在state里。所以枚举i时要先判断(state >> i) & 1是否为1。这个检查如果漏了，dp值可能是初始的无穷大，转移后产生错误结果。

4.3 用暴力对拍验证状压DP的正确性

状压DP的转移逻辑比较复杂，肉眼查错很难。我的习惯是写一个暴力版本（比如DFS枚举所有方案），然后随机生成小规模数据，对拍验证。n≤8的时候，暴力完全跑得动，对拍几百组就能发现大部分逻辑错误。

对拍的框架很简单：随机生成输入，分别跑暴力和状压，比较输出。如果不一样，就把这组数据打出来，手动分析。这个方法帮我抓出过很多隐蔽的bug，比如转移条件写反、边界处理遗漏等。强烈建议每个状压DP题都这么过一遍。

注意：对拍时数据规模要小，但覆盖要全。比如棋盘类要覆盖N=1、M=1、N和M不等、N和M都是奇数等边界情况。路径类要覆盖n=1、n=2、有重边、有自环等情况。

4.4 时间复杂度的估算与优化方向

状压DP的复杂度通常是O(2^n * n)或O(2^n * n^2)。n=20时，2^20约一百万，乘n^2就是四亿，接近时间极限。优化方向有几个：一是剪枝，跳过不可达状态；二是预处理，把能提前算的都算好；三是用更紧凑的数据结构，比如用数组而不是vector存状态。

还有一个技巧是"枚举子集"。有些状压DP需要枚举一个状态的所有子集，朴素的写法是for (sub = state; sub; sub = (sub-1) & state)，这个技巧能把枚举子集的复杂度从O(2^n)降到O(3^n)（所有状态的子集总数）。这个写法很巧妙，(sub-1) & state能保证sub始终是state的子集，且不重不漏地遍历所有子集。

for (int sub = state; sub; sub = (sub - 1) & state) { // 处理sub }

这个技巧在"集合划分""子集和"类问题里非常常用，值得记住。

5. 从这两道题延伸出的状压DP学习路径

5.1 入门到进阶的题目推荐顺序

如果你刚学状压DP，我建议的刷题顺序是：先做蒙德里安的梦想，理解"状态表示占用情况"和"相邻状态兼容性判断"；再做最短Hamilton路径，理解"状态表示访问集合"和"必须记录当前位置"；然后做"炮兵阵地"（棋盘类进阶，状态约束更复杂）；接着做"集合划分"类问题（枚举子集技巧）；最后挑战"插头DP"（状压DP的进阶变体，状态表示轮廓线）。

这个顺序的好处是循序渐进。蒙德里安梦想的状态定义最直观，转移也简单；Hamilton路径引入了"位置"这个额外维度；炮兵阵地引入了"状态之间的约束"（比如相邻格子不能同时放）；集合划分引入了"枚举子集"；插头DP则是把状压用到了极致，状态表示的是"轮廓线上的插头情况"。

5.2 状压DP与其他DP的融合场景

状压DP很少单独出现，它经常和其他DP技巧融合。比如"状压+树形DP"，在树上做状压，状态表示子树内某些节点的选择情况；"状压+数位DP"，在数位上做状压，状态表示已经用了哪些数字；"状压+矩阵快速幂"，当转移是线性的且状态数固定时，可以用矩阵加速。

这些融合场景的共同点是：问题的某个维度天然是"集合"，而其他维度用常规DP处理。识别出"集合维度"是应用状压的关键。比如"给一棵树染色，相邻节点颜色不同，问方案数"，如果颜色数很少，可以把"用了哪些颜色"状压；如果颜色数很多，就不能状压，得换思路。

5.3 实战中如何快速判断一道题该不该用状压

判断标准有三条：第一，问题涉及一个"集合"，且集合大小n不超过20；第二，集合的状态可以用二进制表示，且状态之间的转移可以用位运算描述；第三，问题的规模使得暴力枚举不可行，但2^n级别的状态数可以接受。

如果三条都满足，基本可以确定用状压DP。如果n超过20，就要考虑其他方法，比如折半枚举、贪心、或者发现问题的特殊性质。如果集合状态没法用二进制表示（比如集合元素有重复、或者状态是连续的而非离散的），状压也不适用。

我个人的经验是：看到"每个元素选或不选""经过每个点恰好一次""用某种形状填充棋盘"这类描述，第一反应就是状压。这些描述的共同点是"每个元素的状态是二元的"，天然适合二进制表示。

6. 我在状压DP上踩过的几个真实坑

6.1 状态定义反了导致答案差一倍

做蒙德里安梦想时，我一开始把状态定义成"当前行已经填充的情况"，而不是"被上一行占用的情况"。结果转移时怎么都写不对，因为"当前行已填充"这个状态在转移过程中是变化的，没法作为DP的固定维度。后来改成"被上一行占用"，一下子就通了。

这个坑的本质是：DP的状态必须是"在转移开始前就确定"的量，不能是"转移过程中才确定的"量。当前行的填充方案是在转移中决定的，所以不能作为状态；而上一行留给当前行的约束是转移前就确定的，可以作为状态。这个原则在状压DP里非常重要。

6.2 忘记初始化导致答案偏大

最短Hamilton路径里，我把dp数组全部初始化为0，忘了把除了dp[1][0]之外的状态设为无穷大。结果所有不可达状态的值都是0，转移时min取到了0，答案偏小。后来改成memset成0x3f，问题解决。

这个坑的教训是：状压DP里，不可达状态必须显式设为无穷大，不能依赖默认的0。因为0在路径长度问题里是一个合法值（比如起点到起点距离为0），没法区分"不可达"和"距离为0"。

6.3 位运算写错导致状态判断失效

有一次写if (state & (1 << i) == 0)，本意是判断第i位是否为0，结果因为优先级问题，实际执行的是state & ((1 << i) == 0)，也就是state & 0，永远为0，条件永远为真。这个bug很隐蔽，因为代码看起来"逻辑是对的"，但实际行为完全错误。

从那以后，我养成了所有位运算都加括号的习惯。((state >> i) & 1) == 0这样写，虽然长一点，但绝对不会错。这个习惯帮我省了很多调试时间。

6.4 复杂度估算错误导致超时

有一次做一道状压DP，n=20，我写了个O(2^n * n^2)的算法，觉得四亿次操作应该能过。结果实际跑下来超时了，因为每次操作还包含一些常数较大的运算（比如min、数组访问）。后来优化成O(2^n * n)，把内层的n^2降成n，才勉强过。

这个坑的教训是：状压DP的复杂度估算要保守。2^n * n^2在n=20时是四亿，但实际常数可能让有效操作数翻倍。如果时间限制是1秒，最好把复杂度控制在2^n * n以内。优化方向包括：预处理转移、剪枝不可达状态、用更紧凑的数据结构。

7. 写给正在学状压DP的你

状压DP刚学的时候确实抽象，因为"把集合压进整数"这个操作需要一点想象力。但一旦理解了二进制和集合的对应关系，后面的套路其实很固定。我的建议是：先把蒙德里安梦想和最短Hamilton路径这两道题手推一遍，不要看题解，自己画图模拟状态转移，把每一步的state和dp值都写出来。推完这两道，再看其他状压DP题，会发现思路大同小异。

另外，位运算的熟练度很重要。(state >> i) & 1、state | (1 << i)、state & ~(1 << i)、(sub - 1) & state这几个操作要练到不用想就能写出来。这些是状压DP的基本功，就像学开车要先练好踩离合一样。

最后，多对拍。状压DP的转移逻辑复杂，肉眼查错效率低。写个暴力对拍，随机生成小数据，跑几百组，大部分bug都能抓出来。这个方法虽然笨，但真的有效。我在实际比赛中用对拍救过好几次，尤其是状态转移条件写错的时候，对拍能快速定位到出错的输入。