1. 从“暴力枚举”到“状态压缩”一个思维跃迁如果你刷过一些算法题尤其是动态规划DP相关的大概率遇到过这样的场景题目描述里出现了一个规模不大的集合比如最多20个城市、15个任务、或者一个5x5的棋盘。你直觉上觉得可以用回溯或者DFS去枚举所有可能性但一算时间复杂度2^20 已经超过百万再乘上其他维度妥妥地超时。这时候状态压缩DP就该登场了。我第一次被这个概念“震撼”到是在解决一个经典的“旅行商问题”变种时。题目说有不超过15个城市需要从起点出发每个城市访问一次最后回到起点求最短路径。用DFS回溯15个城市的全排列是15!天文数字。但用状态压缩DP复杂度是O(2^n * n^2)2^15 * 15^2 ≈ 700万完全在可接受范围内。这背后的核心思想就是把一个集合的“选中状态”用一个整数的二进制位来表示。比如有5个城市用二进制数10101就表示第1、3、5个城市已经被访问过了。这个整数就是“状态”。状态压缩DP的精髓在于它用极其紧凑的方式表达了原本需要庞大数组甚至复杂数据结构才能表示的“状态”从而将指数级复杂度的枚举问题转化为在状态空间上进行递推的DP问题。它不是什么全新的算法而是动态规划思想在特定问题模型通常是涉及集合选取、排列组合的NP难问题的小规模实例上的一种高效实现技巧。掌握它相当于在算法工具箱里添了一把处理“小集合大组合”问题的瑞士军刀。2. 状态压缩的核心二进制位运算的妙用理解状态压缩DP第一步是彻底搞懂如何用二进制数来表示和操作一个集合。这不是简单的“知道就行”而是要形成肌肉记忆般的熟练度。2.1 状态表示整数即集合假设我们有一个包含n个元素的集合通常编号为0到n-1编程中从0开始更自然。那么一个整数state的二进制表示的第i位从低位开始就对应集合中第i个元素的状态。通常1表示“选中”、“已访问”、“已放置”0则表示相反。例如n5state 21二进制10101第0位是1 - 元素0被选中第1位是0 - 元素1未选中第2位是1 - 元素2被选中第3位是0 - 元素3未选中第4位是1 - 元素4被选中 所以这个状态表示我们选中了集合{0, 2, 4}。2.2 关键位运算操作这是状态压缩DP的“基本功”必须烂熟于心。以下操作假设我们关注第i位0-indexed。判断第i位是否为1(state i) 1原理将state右移i位使第i位移动到最低位然后与1进行按位与操作。结果为1则表示该位是1。示例判断state21 (10101)的第2位。21 2 5 (00101)5 1 1所以是1。将第i位设置为1state | (1 i)原理先构造一个只有第i位是1的数(1 i)然后与原状态进行按位或操作。或操作的特性是“有1则1”。示例将state16 (10000)的第1位设为1。1 1 2 (00010)16 | 2 18 (10010)。将第i位设置为0state (~(1 i))原理先构造一个除了第i位是0其他位都是1的数~(1 i)~是按位取反然后与原状态进行按位与操作。与操作的特性是“全1则1有0则0”。示例将state21 (10101)的第2位设为0。1 2 4 (00100)~4 ...11111011仅看低5位是1101121 (~4) 17 (10001)。检查状态state是否是另一个状态sub的子集(state sub) sub原理sub是state的子集意味着sub中所有为1的位在state中也必须为1。按位与操作后如果结果仍然等于sub则说明state完全包含了sub。这是解决许多“覆盖”、“包含”类问题的关键判断。枚举状态s的所有子集这是一个非常重要的技巧。for(int sub s; sub; sub (sub - 1) s) { // sub 就是 s 的一个非空子集 } // 如果需要包含空集可以单独处理原理(sub - 1) s这个操作可以高效地得到sub在s中的下一个“按字典序递减”的子集。这个循环会精确地枚举s的所有2^k个子集k是s中1的位数时间复杂度是O(2^k)而不是O(2^n)。这在n20但当前状态中1的位数不多时非常高效。注意在实际编码中尤其是C中要注意运算符优先级。位运算的优先级通常低于比较运算符所以像(state i) 1这样的表达式括号是必须的。一个常见的错误是写成state i 1虽然有时能工作但为了清晰和安全务必加上括号。3. 经典模型一旅行商问题TSP及其变种旅行商问题TSP是状态压缩DP最经典的例题没有之一。它清晰地展示了如何将“路径顺序”这个看似是排列的问题转化为“访问集合”的状态问题。3.1 问题定义与状态设计问题给定一个n个节点的完全图或任意图给出一个邻接矩阵dist[i][j]表示从i到j的距离。求从任意点通常是0号点出发恰好访问所有其他节点一次并回到起点的最短路径长度。n通常不超过20。暴力为何失效如果枚举所有排列(n-1)!当n16时15! ≈ 1.3万亿不可接受。状态压缩DP思路 我们并不关心具体访问的前后顺序只关心已经访问了哪些城市一个集合。当前停留在哪个城市这个城市必须在已访问集合中。因此我们可以定义状态dp[state][i]表示当前已经访问过的城市集合为state二进制表示并且最后停留在城市i时所花费的最小代价。状态转移 当前状态是(state, i)。这个状态是怎么来的一定是从某个没有访问i的状态prev_state从某个城市j走到城市i而来的。其中prev_state state ^ (1 i)即把state中代表i的位去掉。j可以是prev_state中任意一个为1的位即已访问过的城市。 所以转移方程为dp[state][i] min{ dp[prev_state][j] dist[j][i] }对于所有j属于prev_state。初始化dp[1 start][start] 0表示从起点出发只访问了起点目前在起点代价为0。其他状态初始化为无穷大。答案 最终答案是访问所有城市并回到起点。即所有城市都被访问的状态是(1 n) - 1二进制下n个1。我们需要枚举最后一步是从哪个城市i回到起点start。ans min{ dp[(1n)-1][i] dist[i][start] } 其中i遍历所有城市。3.2 代码实现与细节剖析#include bits/stdc.h using namespace std; const int INF 0x3f3f3f3f; int tsp(const vectorvectorint dist, int start) { int n dist.size(); int state_size 1 n; // 状态总数 vectorvectorint dp(state_size, vectorint(n, INF)); // 初始化从起点开始 dp[1 start][start] 0; // 遍历所有状态 for (int state 0; state state_size; state) { // 遍历所有可能的当前城市i for (int i 0; i n; i) { // 如果状态state中不包含城市i则dp[state][i]无效跳过 if (!(state (1 i))) continue; // 如果dp[state][i]还是无穷大说明这个状态目前不可达也无法从中转移出去 if (dp[state][i] INF) continue; // 从当前状态(state, i)出发尝试去下一个未访问的城市j for (int j 0; j n; j) { // 如果j已经访问过(state中第j位为1)或者ij跳过 if (state (1 j)) continue; int next_state state | (1 j); dp[next_state][j] min(dp[next_state][j], dp[state][i] dist[i][j]); } } } // 寻找答案最终状态是全部访问完 (1n)-1最后停在任何城市i然后返回起点 int final_state (1 n) - 1; int ans INF; for (int i 0; i n; i) { if (dp[final_state][i] ! INF) { ans min(ans, dp[final_state][i] dist[i][start]); } } return ans; }关键细节与优化遍历顺序外层循环遍历状态state。为什么这样遍历是对的因为dp[state][i]所依赖的状态dp[prev_state][j]其prev_state是state去掉一个1其二进制表示中1的个数比state少。如果我们按状态值从小到大遍历prev_state一定比state小在遍历到state时已经被计算过了。这是一种隐式的“按集合大小”顺序遍历。空间与时间空间复杂度O(2^n * n)时间复杂度O(2^n * n^2)。当n20时2^20 ≈ 100万n^2400总操作量约4亿在C中经过良好优化通常可以在1秒内完成例如使用-O2编译优化使用数组代替vectorvectorint使用INT_MAX/2代替INF避免加法溢出等。记忆化搜索实现对于某些变种问题如不一定需要回到起点或者起点终点固定用记忆化搜索DFSMemo写起来可能更直观。其本质与递推完全相同只是换了一种计算顺序。3.3 变种问题最短哈密顿路径这是TSP的一个近亲区别在于不需要回到起点求的是从起点到终点的最短哈密顿路径访问所有点恰好一次。状态设计可以和TSP完全一样dp[state][i]表示访问集合state最后在i点的最短路径。初始化dp[1start][start] 0。答案ans dp[(1n)-1][end]即最终状态停在终点end。转移方程与TSP完全相同。这体现了状态定义的通用性。踩坑点在初始化时除了起点状态其他状态应设为无穷大。在转移时一定要先判断dp[state][i]是否有效非无穷大否则用无效状态去更新其他状态会导致错误。另外对于距离矩阵dist需要处理不连通的情况通常也设为无穷大并在转移时判断。4. 经典模型二棋盘覆盖与放置问题这类问题通常在一个网格如N x M的棋盘上进行要求放置若干形状的棋子如骨牌、国王、车要求它们互不冲突。N和M通常较小比如不超过10但状态空间依然巨大。状态压缩DP通过将一行的放置情况压缩为一个状态在行与行之间进行转移。4.1 骨牌铺满棋盘多米诺骨牌问题给定一个N x M的棋盘有些格子有障碍不能放置。用1x2的多米诺骨牌可以横着或竖着放铺满所有没有障碍的格子问有多少种铺法。N, M一般小于等于10。为什么是状态压缩每一行的放置情况会受到上一行放置情况的影响因为竖着放的骨牌会跨越两行。我们可以把每一行用一个M位的二进制数state来表示其中1表示这个位置被一个从上一行延伸下来的竖牌所占据或者说这个位置对当前行来说已经被“占用”了0表示这个位置是空的可以放置新的骨牌。状态设计dp[i][state]表示处理完前i行且第i行的占用状态为state时总的方案数。这里的state表示的是第i行哪些格子被来自第i-1行的竖牌“占据”了。转移过程核心 已知dp[i-1][prev_state]即第i-1行的状态是prev_state。现在我们要决定第i行的放置方式并得到第i行的新状态now_state。我们需要考虑第i行所有可能的放置方式。放置时需要结合第i行本身的障碍情况用row_mask[i]表示有障碍的位为1。第i-1行留下的prev_state表示第i行哪些位置已经被竖牌上半部分占用这些位置不能再放东西。我们要生成第i行的now_state这个状态将传递给下一行表示第i1行哪些位置被第i行放下的竖牌所占用。我们可以通过一个DFS函数来枚举第i行所有合法的放置。从第0列开始逐列放置如果当前位置(i, j)有障碍或者被prev_state占用即prev_state的第j位为1则这个格子不能放骨牌的起点直接考虑下一列。否则有两种选择 a.放一个横着的骨牌如果j1 M且(i, j1)位置无障碍且未被prev_state占用则可以放置。这不会产生新的now_state因为横牌不跨越行。 b.放一个竖着的骨牌这要求(i, j)和(i1, j)都无障碍且(i, j)未被prev_state占用。放置后需要在now_state的第j位标记为1表示这个位置被一个竖牌的下半部分占据了下一行这个位置将被占用。当DFS枚举到最后一列时就得到了一个合法的now_state。那么就可以进行转移dp[i][now_state] dp[i-1][prev_state]。初始化dp[0][0] 1表示第0行之前一个虚拟的行状态为0没有竖牌延伸下来有一种方案什么都不放。答案dp[N][0]表示处理完所有N行后没有竖牌延伸到第N行之外即所有竖牌都完整放置这就是总的方案数。#include bits/stdc.h using namespace std; typedef long long ll; ll dp[12][1 11]; int n, m; int row_mask[12]; // 每一行的障碍掩码 void dfs(int row, int col, int prev_state, int now_state, ll val) { if (col m) { // 枚举完当前行所有列得到一个合法的now_state dp[row][now_state] val; return; } // 情况1当前位置被上一行的竖牌占了或者有障碍只能跳过 if ((prev_state col) 1) { dfs(row, col 1, prev_state, now_state, val); return; } if ((row_mask[row] col) 1) { // 有障碍不能放但如果是被障碍占了对于dp计算这个位置在prev_state里应该是0但实际不能放任何东西 // 我们需要确保prev_state中对应障碍位是0否则这个prev_state本身就不合法。 // 这里我们遇到障碍说明这个格子是空的但不能作为起点直接跳过。 dfs(row, col 1, prev_state, now_state, val); return; } // 情况2放一个横着的骨牌 (1x2) if (col 1 m !((prev_state (col 1)) 1) !((row_mask[row] (col 1)) 1)) { // (col, col1)都空闲且无障碍 dfs(row, col 2, prev_state, now_state, val); } // 情况3放一个竖着的骨牌 (2x1) // 竖牌会影响下一行所以需要在now_state中标记 if (row 1 n) { // 确保有下一行 // 下一行的同一列不能有障碍这个检查通常在下一行的row_mask中但这里我们只关心当前行放置是否合法下一行的障碍在下一轮转移时会处理 // 放置竖牌只需要当前格子和下一行对应格子无障碍。下一行的障碍检查在下一轮dp[row1]时通过row_mask[row1]和now_state来判断。 // 所以这里我们只需要放置并在now_state中标记。 int new_now_state now_state | (1 col); dfs(row, col 1, prev_state, new_now_state, val); } } int main() { while (cin n m n m) { memset(row_mask, 0, sizeof(row_mask)); for (int i 0; i n; i) { for (int j 0; j m; j) { char c; cin c; if (c #) { // 假设#表示障碍 row_mask[i] | (1 j); } } } memset(dp, 0, sizeof(dp)); dp[0][0] 1; // 初始化 for (int i 0; i n; i) { for (int prev_state 0; prev_state (1 m); prev_state) { if (dp[i][prev_state] 0) continue; // 无效状态跳过 // 枚举当前行i在上一行状态为prev_state时所有可能的放置得到当前行状态now_state dfs(i, 0, prev_state, 0, dp[i][prev_state]); } } // 最终答案第n行0-indexed即处理完所有行后的状态为0没有竖牌延伸出去 cout dp[n][0] endl; } return 0; }注意这是轮廓线DP的一种简化形式按行递推。实际更高效的是轮廓线DP插头DP它逐格递推状态表示当前处理格子的轮廓线即当前格左边和上边的格子对后续的影响。但按行递推的状态压缩DP更容易理解是学习轮廓线DP的重要基础。4.2 小国王互不攻击问题在N x N的棋盘上放K个国王国王可以攻击相邻的8个格子。要求国王之间互不攻击求方案数。N 10, K N^2。状态设计由于国王的攻击范围是周围一圈所以第i行的放置方案只受第i-1行和第i-2行影响实际上因为攻击范围是相邻行所以第i行只与第i-1行直接相关。我们可以定义dp[i][j][state]表示处理完前i行已经放置了j个国王且第i行的放置状态为state时的方案数。state是一个二进制数1表示放国王0表示不放。合法性检查行内合法状态state不能有相邻的1即(state (state 1)) 0。行间合法第i行的状态now与第i-1行的状态prev不能相互攻击。即上下不能同时为1(now prev) 0左上右下斜角不能同时为1(now (prev 1)) 0且(now (prev 1)) 0综合起来就是(now prev) 0 (now (prev 1)) 0 (now (prev 1)) 0。可以简化为(now (prev | (prev 1) | (prev 1))) 0。转移dp[i][j][now] dp[i-1][j - count(now)][prev]其中count(now)是状态now中1的个数即该行放的国王数prev是上一行的合法状态且满足行间合法性。初始化dp[0][0][0] 1表示第0行虚拟行之前放了0个国王状态为0不放有1种方案。也可以认为dp[0][count(state)][state] 1其中state是任意一个行内合法的状态。答案sum(dp[N][K][state])对所有合法的state求和。优化我们可以预处理出所有行内合法的状态称为valid_states以及每个状态中1的个数king_count[s]和任意两个合法状态之间是否满足行间合法性compatible[a][b]。这样在DP转移时只需要遍历预处理好的状态集合可以大幅减少无效枚举。#include bits/stdc.h using namespace std; typedef long long ll; ll dp[12][105][1 10]; // dp[i][j][s] vectorint valid_states; int king_count[1 10]; bool compatible[1 10][1 10]; int count_bits(int x) { int cnt 0; while (x) { cnt; x (x - 1); // 经典操作去掉最低位的1 } return cnt; } int main() { int N, K; cin N K; // 1. 预处理所有行内合法状态 for (int s 0; s (1 N); s) { if (s (s 1)) continue; // 有相邻的1不合法 valid_states.push_back(s); king_count[s] count_bits(s); } int S valid_states.size(); // 2. 预处理状态间兼容性 for (int i 0; i S; i) { for (int j 0; j S; j) { int a valid_states[i], b valid_states[j]; if ((a b) || (a (b 1)) || (a (b 1))) { compatible[i][j] false; } else { compatible[i][j] true; } } } // 3. DP初始化 dp[0][0][0] 1; // 第0行虚拟行状态为0放了0个国王 // 另一种初始化dp[1][count(s)][s] 1 for s in valid_states // 4. DP转移 for (int i 1; i N; i) { // 处理到第i行 for (int j 0; j K; j) { // 已经放置的国王总数 for (int cur_idx 0; cur_idx S; cur_idx) { // 当前行状态 int cur_state valid_states[cur_idx]; int cur_kings king_count[cur_state]; if (cur_kings j) continue; // 当前行放的国王数已经超过总数不可能 for (int prev_idx 0; prev_idx S; prev_idx) { // 上一行状态 if (!compatible[prev_idx][cur_idx]) continue; int prev_state valid_states[prev_idx]; dp[i][j][cur_state] dp[i-1][j - cur_kings][prev_state]; } } } } // 5. 统计答案 ll ans 0; for (int s : valid_states) { ans dp[N][K][s]; } cout ans endl; return 0; }经验之谈对于棋盘放置问题预处理是一个极其重要的优化手段。把行内合法性检查、状态中1的个数、状态间兼容性都预先计算好并存储起来DP过程就会变成简单的查表累加代码清晰且高效。否则在DP的三重循环内做这些检查和计算会大大增加常数时间可能导致超时。5. 状态压缩DP的优化技巧与常见陷阱当状态空间达到2^20量级约100万时时间和空间都变得紧张。掌握一些优化技巧至关重要。5.1 滚动数组优化空间这是最常用的空间优化。观察状态转移方程dp[i][...]通常只依赖于dp[i-1][...]。因此我们只需要两个数组或者一个二维数组的两行来回滚动即可空间复杂度从O(2^n * n)降为O(2^n)。// 以TSP为例使用滚动数组 vectorvectorint dp(2, vectorint(1n, INF)); int cur 0, nxt 1; dp[cur][1start][start] 0; for (int ...) { // 某种遍历顺序 fill(dp[nxt].begin(), dp[nxt].end(), INF); // 清空下一层 for (int state ...) { for (int i ...) { if (dp[cur][state][i] INF) continue; // ... 转移更新 dp[nxt][new_state][j] } } swap(cur, nxt); // 滚动 }5.2 枚举子集优化时间在有些问题中我们需要枚举一个状态的所有子集。直接枚举0到state的所有数并判断是否是子集复杂度是O(2^n)非常低效。使用for(int sub state; sub; sub (sub-1) state)这个技巧可以精确枚举state的所有子集复杂度是O(2^k)其中k是state中1的个数。这在很多“集合划分”、“子集贡献”问题中能起到决定性优化作用。例题集合划分。将n个物品划分成若干组每组内部有代价求最小总代价。状态state表示已分配的物品集合。我们需要枚举state的一个非空子集group作为最后一组代价为cost[group]那么dp[state] min{ dp[state ^ group] cost[group] }。使用子集枚举优化后总复杂度从O(3^n)降为O(2^n * 2^(n/2))级别更精确是O(∑C(n,k)*2^k)在n16时差异巨大。5.3 位运算优先级陷阱这是新手最容易出错的地方。、|、、等位运算符的优先级低于、!等比较运算符也低于、-。错误示例if (state 1 0)本意是判断最低位是否为0。但实际上会先计算1 0结果为false即0再计算state 0结果永远为0条件永远为真正确写法if ((state 1) 0)。任何时候对位运算表达式做比较务必加上括号。5.4 状态定义与初始化状态定义是DP的灵魂。定义不好可能导致转移复杂、状态数爆炸或者无法表示最终答案。思考维度状态需要包含哪些信息才能唯一确定一个“子问题”并向后转移通常包括已处理的元素集合压缩、当前所在位置、已使用的某种资源数量如已放置的国王数K、以及可能需要的其他辅助信息如最后两个元素是什么用于处理某些特殊限制。初始化dp[起点状态] 0其他状态为无穷大求最小值时或0求方案数时。确保起点状态是合法的、可开始的状态。最终答案不一定对应某个单一的dp[state][...]可能是对所有满足最终条件的状态取min或sum。要仔细读题明确“完成”意味着什么状态属性。5.5 内存与时间估算在动手前先估算一下。状态数通常是2^n * (其他维度)。如果n202^20 ≈ 1e6。如果再乘一个n20就是2千万状态。每个状态如果是int占用4字节那么内存就是80MB可能接近空间限制。这时要考虑滚动数组优化或者用short如果值范围允许。时间复杂度状态数 * 每个状态的转移数。如果转移需要枚举所有城市O(n)或者枚举子集O(2^k)需要估算最坏情况。2^20 * 20^2 ≈ 4e8在2秒时限内C优化后有可能通过但已经非常极限。需要考虑是否有优化可能比如提前剪枝无效状态或者改变DP顺序。6. 实战例题精解从读题到AC的完整思考链路我们通过一个具体问题将上述所有知识点串联起来。选择LeetCode 698“划分为k个相等的子集”的变种或类似题目但为了更贴合状态压缩我们看一个经典问题“最短超串”。问题描述你有n个字符串words。你的任务是找出一个最短的字符串使得这n个字符串都是它的子串。你可以任意排列这些字符串并可以重叠拼接。n 12每个字符串长度不超过50。为什么用状态压缩n最大为12我们需要决定字符串的排列顺序。暴力枚举排列是12!巨大。但我们可以用状态压缩DP来记录“已经使用了哪些字符串”以及“最后一个字符串是哪个”。第一步预处理节省计算直接拼接字符串并计算最短超串长度很麻烦。一个关键优化是预处理出任意两个字符串words[i]和words[j]当i后面接j时j可以重叠在前一个i的尾部多少字符。记overlap[i][j]为i的后缀与j的前缀的最大匹配长度。 例如iabcde,jcdefg最大重叠是cde长度为3。 计算overlap可以用简单的双重循环匹配或者更高效的KMP思想但因为字符串长度≤50双重循环足矣。第二步状态设计与DP定义dp[state][i]表示已经使用的字符串集合为state二进制位表示且最后使用的字符串是i时所能形成的最短超串长度。 这里state的第i位一定是1因为i是最后一个使用的它肯定在集合里。第三步状态转移考虑状态(state, i)。我们想在这个超串后面再接一个字符串jj不在state中。 新的超串长度会增加多少不是len(words[j])而是len(words[j]) - overlap[i][j]。因为j的前overlap[i][j]个字符可以和i的尾部重叠。 所以转移方程为dp[state | (1j)][j] min( dp[state | (1j)][j], dp[state][i] len(words[j]) - overlap[i][j] )第四步初始化最开始我们可以认为从一个“空字符串”开始。那么对于每个字符串i如果它作为第一个字符串超串长度就是它自身的长度。dp[1i][i] len(words[i])第五步答案最终我们需要所有字符串都被使用即state (1n)-1。答案就是min{ dp[(1n)-1][i] }对所有i取最小值。第六步路径还原如果需要输出超串本身DP通常只求最优值。要求出具体方案需要记录每个状态是从哪个前驱状态转移而来的。我们可以用pre_state[state][i]和pre_char[state][i]来记录到达(state, i)的前一个字符串是什么。然后从最终状态倒推回去根据overlap信息拼接字符串。代码框架int shortestSuperstring(vectorstring words) { int n words.size(); // 1. 预处理overlap vectorvectorint overlap(n, vectorint(n, 0)); for (int i 0; i n; i) { for (int j 0; j n; j) { if (i j) continue; int len min(words[i].size(), words[j].size()); for (int k len; k 0; --k) { if (words[i].substr(words[i].size() - k) words[j].substr(0, k)) { overlap[i][j] k; break; } } } } // 2. DP初始化 int state_size 1 n; vectorvectorint dp(state_size, vectorint(n, INF)); for (int i 0; i n; i) { dp[1 i][i] words[i].size(); } // 3. DP转移 for (int state 1; state state_size; state) { for (int i 0; i n; i) { if (!(state (1 i))) continue; // i不在状态中无效 if (dp[state][i] INF) continue; for (int j 0; j n; j) { if (state (1 j)) continue; // j已经在状态中跳过 int new_state state | (1 j); int new_len dp[state][i] words[j].size() - overlap[i][j]; if (new_len dp[new_state][j]) { dp[new_state][j] new_len; // 如果需要记录路径在这里记录pre_state[new_state][j] i; } } } } // 4. 找答案 int final_state state_size - 1; int ans INF; int last -1; for (int i 0; i n; i) { if (dp[final_state][i] ans) { ans dp[final_state][i]; last i; } } // 5. 利用记录的路径还原字符串略 return ans; }思考与扩展如果n更大比如152^15 * 15 * 15 ≈ 700万次转移每次转移计算overlap是O(L)L是字符串长度可能超时。所以预处理overlap矩阵至关重要将转移代价降为O(1)。这个问题本质上是一个“有重叠的哈密顿路径”问题目标是路径权重总长度减去重叠长度最小。和TSP神似。如果不需要输出具体字符串只求长度上述DP足够。如果需要输出路径还原是很好的练习。状态压缩DP的题目千变万化但核心脉络不变识别问题中的“小集合”定义包含该集合状态的状态设计合理的转移方程利用位运算高效实现并注意时间和空间的优化。从TSP到棋盘覆盖再到字符串排列其内核都是对指数级状态空间的智慧枚举。多练习多总结这种“将集合压入整数”的思维就会成为你解决组合优化问题的利器。