1. 项目概述从“状态爆炸”到“压缩求解”的思维跃迁如果你刷过一些算法题尤其是动态规划DP相关的大概率遇到过这种场景题目描述一个模型比如在一个网格上放置物品要求相邻位置不能同时放置问有多少种方案。你直觉上觉得可以用DP设dp[i][state]表示处理到第i行时该行的放置状态为state的方案数。但问题来了这个state怎么表示如果一行有m个位置每个位置有“放”或“不放”两种可能那么state就有2^m种可能性。当m达到10、15甚至20时状态数量直接指数爆炸常规的数组表示和遍历根本吃不消。状态压缩动态规划就是专门用来对付这类“状态空间巨大但状态本身信息量不大”问题的利器。它的核心思想非常巧妙既然每个位置的状态通常只是有限的几种比如放/不放有/无那么我们可以用一个整数的二进制位来“压缩”表示这一整行的状态。一个int类型有32位理论上就能表示一行最多32个格子的状态2^32虽然是个天文数字但实际有效状态数往往远小于此我们通过预筛选和位运算技巧可以高效地进行状态转移。我最初接触状态压缩DP是在做“炮兵阵地”那道经典题时被其精妙的设计所震撼。它不像背包DP那样直观更像是一种“用编码思维解决组合优化问题”的艺术。掌握了它你就能打开一扇新的大门去解决一系列涉及排列、覆盖、棋盘摆放等复杂约束的题目。这篇文章我将结合自己踩过的坑和刷题经验为你拆解状态压缩DP的核心心法并用几道经典例题带你从理解到实战。2. 核心思想与前置知识为什么是“压缩”在深入例题之前我们必须夯实基础。状态压缩DP的“压缩”二字是理解其一切技巧的起点。2.1 状态压缩的本质信息编码动态规划的核心是定义“状态”和“状态转移方程”。在常规DP中状态通常用一维或多维数组的下标来表示每个维度代表一个变量如dp[i][j]。但当状态中的某个维度本身就是一个“集合”或“配置”时比如一行格子的摆放情况直接将其作为数组维度会导致维度过高。状态压缩的做法是将一个多维的、描述组合情况的状态编码成一个单一的整数。最常用、最自然的就是二进制编码。举个例子假设一行有5个格子我们要表示每个格子是否有棋子。常规思路是定义一个长度为5的数组arr[5]arr[k]1表示第k个格子有棋子。在状态压缩中我们用一个5位的二进制数来表示。例如二进制数10101十进制21表示第1、3、5个格子有棋子通常最低位代表最右边的格子。这样一个整数就“压缩”携带了一整行的全部信息。2.2 必须掌握的位运算工具箱位运算是操作压缩状态的“手术刀”以下操作必须形成肌肉记忆获取第k位的值从0开始计数(state k) 1state k将第k位移动到最低位。 1用于取出最低位的值。意图判断状态state中第k个位置是否为1。将第k位设置为1state | (1 k)1 k生成一个只有第k位是1其他位是0的数。|或运算可以将state的第k位强制设为1其他位不变。意图构造一个新状态表示在第k个位置放置了物品。将第k位设置为0state (~(1 k))~(1 k)是1 k的按位取反结果是一个第k位为0其他位为1的数。与运算可以将state的第k位清零其他位保留。意图构造一个新状态表示第k个位置为空。检查状态state中是否有连续的1(state (state 1)) 0state 1将状态左移一位如果原状态中有相邻的1那么左移后这两个1就会在同一位置重合。操作后结果不为0就说明存在相邻的1。意图常用于判断同一行内放置的物品是否相邻这是很多题目的约束条件。判断状态a和状态b在同一列是否冲突(a b) 0如果两个状态在相同位都是1操作后该位为1结果不为0说明冲突。意图常用于判断上下两行的放置是否在垂直方向冲突。判断状态a是否为状态b的子集(a b) a这意味着b在a为1的所有位上也都为1。意图在覆盖类问题中判断当前行的状态是否能被上一行的状态所“覆盖”。枚举状态s的所有子集sub s while sub 0: # 处理子集 sub sub (sub - 1) s # 不要忘记空集这是一个非常经典的技巧复杂度是O(3^n)而非O(4^n)在集合划分DP中极其有用。实操心得刚开始时建议在纸上画一画二进制位。比如对于state 21 (10101)手动计算一下state 2 1是多少state | (1 2)又变成了多少。这个过程能帮你快速建立二进制位和实际含义的对应关系避免后续写代码时思路混乱。2.3 状态压缩DP的通用解题框架尽管题目千变万化但状态压缩DP的思考路径有章可循确定压缩维度首先要识别问题中哪个维度通常是一行、一列或一个阶段的状态可以用二进制压缩。最常见的是“行”我们将一行的配置压缩成一个整数state。预处理有效状态不是所有2^m个状态都是合法的。例如棋盘放置中同一行内棋子不能相邻。我们需要提前枚举所有满足“行内约束”的合法状态并存储起来。这能大幅减少后续DP转移时需要遍历的状态数。设计DP状态定义通常是dp[i][state]表示处理到第i个压缩维度如第i行且该维度的状态为state时题目所求的值方案数、最大值、最小值等。有时需要增加维度如dp[i][state1][state2]表示第i-1行和第i行的状态。推导状态转移方程这是核心。考虑从dp[i-1][prev_state]如何转移到dp[i][curr_state]。转移的条件是prev_state和curr_state必须满足“行间约束”如不能上下冲突。转移的值通常是累加或取最优。处理边界与初始化通常dp[0][state]需要根据第一行的合法状态进行初始化。有些题目需要虚拟第0行其状态为0空行。计算最终答案根据DP状态定义对所有可能的最终状态state的dp[n][state]进行求和或取最优。3. 经典例题精解从入门到进阶理论讲再多不如看实战。下面我们通过三道经典题目由浅入深地掌握状态压缩DP。3.1 例题一AcWing 291. 蒙德里安的梦想棋盘覆盖题目简述给定一个N x M的棋盘用1x2的长方形骨牌要么横着放覆盖相邻两格要么竖着放铺满整个棋盘求方案数。1 ≤ N, M ≤ 11。思路拆解 这道题是状态压缩DP的“启蒙题”。核心在于当所有横放的骨牌确定后竖放的骨牌位置也就唯一确定了只能填满剩下的空格。因此我们只需要计算“只放横牌”的合法方案数。压缩维度按列进行压缩。dp[i][state]表示当前处理到第i列且第i列的“突出情况”为state时的方案数。state是一个M位的二进制数如果第j行有一个从第i-1列横着伸到第i列的骨牌即占了第i列第j行这个格子那么state的第j位就是1。状态转移从dp[i-1][prev]转移到dp[i][curr]。prev表示第i-1列伸出来的情况curr表示第i列伸出来的情况。转移是否合法需要满足两个条件列内冲突prev curr 0。即同一行不能同时被从左右两边伸出来的横牌占据。剩余空间可填竖牌prev | curr这个状态表示第i-1列被横牌占据的位置。那么第i-1列剩下的、连续的空格必须是偶数个因为竖牌是1x2的。换句话说prev | curr这个二进制数中连续的0的个数必须是偶数。预处理我们可以提前预处理出对于每一个状态s它是否满足“连续0为偶数”这个条件。同时对于每个状态curr预处理出所有能转移到它的合法prev状态列表。初始化与答案dp[0][0] 1表示第0列一个不存在的虚拟列没有伸出来的骨牌这是一种基础状态。最终答案是dp[M][0]表示处理完最后一列第M列并且没有任何骨牌伸到棋盘外面。核心代码片段C风格伪代码const int N 12, M 1 N; long long dp[N][M]; vectorint state_trans[M]; // state_trans[curr] 存储所有合法的prev bool is_valid[M]; // 标记状态s的连续0是否为偶数 // 预处理 is_valid for (int s 0; s 1 n; s) { int cnt 0; bool valid true; for (int j 0; j n; j) { if (s j 1) { if (cnt 1) { valid false; break; } cnt 0; } else { cnt; } } if (cnt 1) valid false; is_valid[s] valid; } // 预处理状态转移关系 for (int curr 0; curr 1 n; curr) { state_trans[curr].clear(); for (int prev 0; prev 1 n; prev) { if ((curr prev) 0 is_valid[curr | prev]) { state_trans[curr].push_back(prev); } } } // DP过程 dp[0][0] 1; for (int i 1; i m; i) { for (int curr 0; curr 1 n; curr) { for (int prev : state_trans[curr]) { dp[i][curr] dp[i-1][prev]; } } } cout dp[m][0] endl;踩坑记录这道题最大的坑在于数据范围和初始化。N, M 11状态数最多2^11 2048DP数组是12 * 2048看起来不大。但方案数可能非常巨大必须使用long long存储。另外每次计算前一定要清空DP数组因为有多组测试数据。dp[0][0]1这个初始化非常关键它代表了“空棋盘”这一种基础方案。3.2 例题二AcWing 1064. 小国王棋盘放置题目简述在N x N的棋盘上放K个国王国王可以攻击相邻的8个格子。要求国王之间不能互相攻击求摆放方案数。1 ≤ N ≤ 10, 0 ≤ K ≤ N^2。思路拆解 这道题引入了“数量”这个维度是状态压缩DP的经典扩展。压缩维度按行压缩。dp[i][j][state]表示处理到第i行已经放置了j个国王且第i行的放置状态为state的方案数。预处理有效状态首先同一行内国王不能相邻即状态s需要满足(s (s 1)) 0。同时我们可以预处理出每个合法状态s里包含的国王数量cnt[s]即二进制中1的个数可用__builtin_popcount或预计算。状态转移从dp[i-1][j-c][prev]转移到dp[i][j][curr]。转移条件有两个行间攻击上下两行国王不能在同一列、左上、右上相邻。即(curr prev) 0且(curr (prev 1)) 0且(curr (prev 1)) 0。可以合并为(curr prev) 0 ((curr 1) prev) 0 ((curr 1) prev) 0。国王数量当前行放置的国王数为cnt[curr]所以上一行结束时国王数应为j - cnt[curr]。初始化与答案dp[0][0][0] 1表示第0行虚拟行放了0个国王状态为空。最终答案是sum(dp[N][K][state])对所有合法的第N行状态state求和。核心优化可以提前预处理出每个合法状态a可以转移到哪些合法状态b即满足行间不攻击条件并存储为vectorint head[a]。这样DP时直接遍历这个列表比双重循环判断所有状态要快。国王数量j的循环范围可以从cnt[curr]到K。代码关键部分vectorint valid_states; vectorint state_cnt; vectorint head[M]; // M为合法状态数量 // 预处理合法状态及其国王数 for (int s 0; s 1 n; s) { if (s (s 1)) continue; // 行内相邻 valid_states.push_back(s); state_cnt.push_back(__builtin_popcount(s)); } int sc valid_states.size(); // 预处理状态转移关系 for (int i 0; i sc; i) { for (int j 0; j sc; j) { int a valid_states[i], b valid_states[j]; if ((a b) 0 ((a 1) b) 0 ((a 1) b) 0) { head[i].push_back(j); // 状态i可以转移到状态j } } } // DP过程 dp[0][0][0] 1; // dp[行][已用国王数][状态索引] for (int i 1; i n; i) { for (int j 0; j k; j) { for (int curr_idx 0; curr_idx sc; curr_idx) { int curr_cnt state_cnt[curr_idx]; if (j curr_cnt) continue; for (int prev_idx : head[curr_idx]) { dp[i][j][curr_idx] dp[i-1][j - curr_cnt][prev_idx]; } } } } // 统计答案 long long ans 0; for (int idx 0; idx sc; idx) { ans dp[n][k][idx]; }实操心得这里用“状态索引”代替“状态值”来作为DP数组的一维是一个常用优化。因为合法状态数远小于2^n用索引访问更快且方便预处理转移关系。另外__builtin_popcount是GCC/Clang的内建函数用于快速计算二进制中1的个数在竞赛中非常实用。如果追求可移植性可以自己预计算一个popcount数组。3.3 例题三AcWing 327. 玉米田带障碍的棋盘放置题目简述M x N的农田有些格子是肥沃的可以种草有些是贫瘠的不能种草。现在要种草要求所有草不能相邻上下左右四个方向。求种植方案数。思路拆解 这道题在“小国王”的基础上增加了“地形限制”即每一行有一个固有的“可行状态掩码”。这更贴近实际问题。压缩维度与地形处理按行压缩。我们需要用一个数组g[i]来表示第i行的地形。将肥沃土地视为1贫瘠土地视为0。那么g[i]本身就是一个二进制数。一个放置状态state在第i行是合法的必须满足(state ~g[i]) 0即不能在贫瘠的土地g[i]中为0的位上种草。等价于(state | g[i]) g[i]即state必须是g[i]的一个子集。DP状态定义dp[i][state]表示处理到第i行且第i行种植状态为state的方案数。状态转移从dp[i-1][prev]转移到dp[i][curr]。条件为curr是g[i]的子集行内地形合法。prev是g[i-1]的子集上一行状态自身合法。(curr prev) 0上下两行不冲突。预处理对于每一行i我们预处理出该行所有合法的状态集合states[i]。即所有是g[i]子集且满足行内不相邻(s (s 1)) 0的状态s。同时对于相邻的两行预处理出行间合法的转移对。初始化与答案我们可以虚拟一个第0行其状态为0不种任何草且dp[0][0] 1。最终答案是sum(dp[M][state])对所有第M行的合法状态求和。代码结构亮点vectorint states[MAXM]; // states[i] 存储第i行所有合法状态 vectorint head[MAXM][MAXS]; // head[i][curr_idx] 存储第i-1行能转移到第i行状态curr_idx的状态索引 // 预处理每一行的合法状态 for (int i 1; i m; i) { for (int s 0; s 1 n; s) { if ((s ~g[i]) 0 (s (s 1)) 0) { states[i].push_back(s); } } } // 为了方便第0行加入一个空状态0 states[0].push_back(0); // 预处理状态转移关系 (i从1开始) for (int i 1; i m; i) { for (int curr_idx 0; curr_idx states[i].size(); curr_idx) { int curr states[i][curr_idx]; for (int prev_idx 0; prev_idx states[i-1].size(); prev_idx) { int prev states[i-1][prev_idx]; if ((curr prev) 0) { head[i][curr_idx].push_back(prev_idx); } } } } // DP过程 dp[0][0] 1; // dp[行索引][该行状态在states中的索引] for (int i 1; i m; i) { for (int curr_idx 0; curr_idx states[i].size(); curr_idx) { for (int prev_idx : head[i][curr_idx]) { dp[i][curr_idx] (dp[i][curr_idx] dp[i-1][prev_idx]) % MOD; } } } // 统计答案 int ans 0; for (int idx 0; idx states[m].size(); idx) { ans (ans dp[m][idx]) % MOD; }注意事项这道题模数通常给定如1e8记得每次加法后取模。预处理“行内合法状态”时条件(s ~g[i]) 0是关键它确保了状态s的“1”只出现在肥沃土地上。这种“掩码”思想在状态压缩中非常普遍。4. 状态压缩DP的进阶技巧与变形掌握了上述经典模型我们可以应对大多数棋盘类问题。但状态压缩DP的威力不止于此。4.1 旅行商问题TSP的状态压缩解法TSP问题是给定n个城市和两两之间的距离从某个城市出发访问每个城市恰好一次后回到起点求最短路径。状态定义dp[state][i]表示当前已经访问过的城市集合为state二进制位为1表示已访问并且最后停留在城市i的最短路径长度。state是一个n位的二进制数。i的取值范围是0到n-1。状态转移dp[state][i] min{ dp[prev_state][j] dist[j][i] }其中prev_state是state去掉城市i后的状态即prev_state state ^ (1 i)且j是prev_state中的某个城市即(prev_state j) 1为真。初始化dp[1 start][start] 0表示从起点出发只访问了起点目前在起点距离为0。其他状态初始化为无穷大。答案最终答案是访问所有城市后回到起点的最短距离即min{ dp[(1n)-1][i] dist[i][start] }对所有城市i取最小值。复杂度状态数O(2^n * n)转移复杂度O(n)总复杂度O(2^n * n^2)。当n 20时这个解法是可行的。int n 20; int dist[N][N]; int dp[1N][N]; memset(dp, 0x3f, sizeof(dp)); dp[10][0] 0; // 假设从城市0出发 for (int state 0; state (1 n); state) { for (int i 0; i n; i) { if (!(state i 1)) continue; // 状态state必须包含i int prev_state state ^ (1 i); for (int j 0; j n; j) { if (!(prev_state j 1)) continue; // prev_state必须包含j dp[state][i] min(dp[state][i], dp[prev_state][j] dist[j][i]); } } } int ans INF; int full_state (1 n) - 1; for (int i 0; i n; i) { ans min(ans, dp[full_state][i] dist[i][0]); }性能提示TSP的DP实现中可以优先枚举state再枚举i。并且对于每个state可以预处理出其中包含的所有城市列表避免内层循环每次都判断(state i 1)能带来常数优化。当n20时2^20 ≈ 1e6n^2400总运算量约4e8在优化良好的C中通常可以在2秒内通过。4.2 集合划分DP枚举子集的技巧有一类问题需要将一个集合划分成若干满足条件的子集。例如给定一个数组能否将其划分成两个和相等的子集或者给定n个任务和m个相同的机器求完成所有任务的最短时间任务分配。对于“能否划分成两个和相等的子集”这类问题可以用布尔型DPdp[state]表示能否用集合state中的元素凑出某个和。状态转移时需要枚举state的所有子集。这里就用到前面提到的枚举子集的经典技巧for (int sub state; sub; sub (sub - 1) state) { // sub 是 state 的一个非空子集 int other state ^ sub; // state 的另一个子集 // 进行状态转移判断... } // 如果需要包含空集单独处理这个循环能高效地枚举state的所有子集其时间复杂度是O(3^n)对于n 15的问题是可以接受的。4.3 轮廓线DP插头DP简介当棋盘类问题的约束不仅限于相邻行还可能涉及更复杂的连通性时比如铺放回路、覆盖所有格子且形成一条路径就需要更强大的工具——轮廓线DP也称插头DP。它压缩的状态不再是完整的一行而是当前处理格子的“轮廓线”上的一系列插头状态表示路径的进出情况。轮廓线DP难度较大但其核心思想仍是状态压缩只是状态的设计和转移更为复杂。通常用一个“括号表示法”或“最小表示法”来编码轮廓线上多个插头之间的连通关系。学习轮廓线DP建议从“哈密顿路径”或“棋盘覆盖中的回路问题”入手理解“插头”和“轮廓线”的概念。5. 常见问题、调试技巧与优化策略5.1 为什么我的程序输出0或者答案特别小这是新手最常见的问题大概率是初始化或状态转移条件有误。检查初始化dp[0][0]或dp[0][0][0]是否设为1对于计数问题或0对于最优值问题虚拟的第0行状态通常设为“空状态”。检查状态合法性你的“预处理合法状态”函数是否正确特别是行内约束(s (s 1)) 0是否写成了(s (s 1)) 1这是笔误高发区。检查行间转移条件上下行冲突判断是否完整例如“小国王”需要判断三个方向漏掉一个就会多算很多非法方案。检查地形掩码在“玉米田”这类题中(state ~g[i]) 0这个条件是否遗漏这会导致在贫瘠土地上种草的非法状态被计入。使用打印调试在DP循环中打印出前几行、前几个状态的DP值手动验算一下是否正确。特别是i1时的值它完全由初始化和第一行的合法状态决定很容易验证。5.2 如何优化状态压缩DP的性能预处理预处理还是预处理这是最重要的优化。不要在主DP循环中进行复杂的条件判断如检查状态是否合法、检查两状态是否冲突。提前计算出所有合法状态valid_states并预处理出状态间的转移关系head[curr]。这样DP循环内部就只剩下简洁的累加或取最值操作。使用状态索引DP数组的第二或第三维不要直接用状态值state范围是0到2^n-1而用该状态在valid_states数组中的下标idx。这能大幅减少内存占用和缓存不命中因为合法状态数远小于2^n。滚动数组优化由于dp[i][...]只依赖于dp[i-1][...]可以使用滚动数组将空间复杂度从O(n * 2^n)降为O(2^n)。通常用dp[2][...]或两个数组cur[...],pre[...]交替使用。剪枝在循环中如果某些状态在当前的i或j下明显不可能可以continue。例如在“小国王”中如果当前已放置国王数j小于当前状态curr的国王数cnt[curr]则不可能转移。位运算技巧熟练使用内建函数如__builtin_popcount(GCC/Clang) 或__popcnt(MSVC) 来快速计算二进制中1的个数。对于判断状态是否有连续1(s (s 1)) 0比循环判断每一位要快得多。5.3 状态压缩DP的适用场景与边界适用场景问题规模中有一个维度m较小通常m 20或25并且这个维度的每个单元只有有限的几种状态2-3种。典型问题包括棋盘摆放、覆盖、路径计数、集合划分、任务调度等。时间复杂度通常是O(n * 2^m * T)其中n是另一个维度如行数T是状态转移的复杂度。当m20时2^20 ≈ 1e6这就要求n和T不能太大。空间复杂度O(n * 2^m)或优化后的O(2^m)。使用滚动数组是应对空间限制的常用手段。思维难点最难的一步是将实际问题抽象成“状态”并用二进制表示。需要多做练习培养这种“编码”思维。状态压缩DP就像一把精巧的钥匙专门用来打开那些状态空间看似庞大、但内在结构规整的问题之锁。它要求我们对位运算有深刻的理解对问题有清晰的建模能力。从“蒙德里安的梦想”开始一步步攻克“小国王”、“玉米田”再到尝试TSP和集合划分你会逐渐体会到这种“化繁为简”的思维之美。在调试时耐心地验证每一个预处理结果和转移条件在优化时有意识地使用索引和滚动数组。记住所有复杂的算法拆解到底层都是对状态和转移的精确管理。