1. 从一道国赛真题说起当“最优包含”遇上“编辑距离”最近在整理蓝桥杯国赛的历年真题时我又翻到了那道经典的“最优包含”问题。说实话第一次看到这个题目名字很多同学可能会有点懵——“包含”就包含怎么还“最优”呢但如果你对动态规划DP稍有了解尤其是听说过“编辑距离”这个经典模型那么这道题的思路就会瞬间清晰起来。它本质上就是编辑距离问题的一个精巧变种或者说是一个“限定操作”的子集。这道题在国赛中出现其考察意图非常明确它不满足于让你死记硬背编辑距离的模板代码而是希望你真正理解状态转移方程背后的逻辑并能够根据题目的特殊要求在这个问题里通常只允许“修改”操作或者对操作有特定代价定义进行灵活调整和优化。很多人在学习DP时会陷入“背板子”的误区题目稍微一变就束手无策。“最优包含”恰恰是检验你是否“学活了”的试金石。简单来说“最优包含”问题可以这样描述给定两个字符串S和T我们希望通过最少的操作次数使得字符串S“包含”字符串T。这里的“包含”不是简单的子串匹配而是允许你对S进行一系列编辑操作如修改某个字符最终让T成为S的一个子序列注意是子序列不是连续子串。而“最优”指的就是使用的总操作代价最小。为什么说它和编辑距离亲如兄弟因为编辑距离求解的是将字符串A完全转换成字符串B的最小代价操作包括增、删、改。而“最优包含”可以看作为了在A中“找到”或“匹配出”B我们只关心A中与B对应的部分对于A中其他多余的字符我们可以通过“忽略”类似于编辑距离中的删除但代价可能为0来处理核心操作往往集中在“修改”不对应的字符上。这样一来它的状态定义和转移方程就与编辑距离有着千丝万缕的联系但又需要你重新思考状态的含义。接下来我将彻底拆解这个问题。我们不会停留在AC代码的层面而是要深入其DP状态设计的骨髓理解每一种定义方式背后的视角并对比它们的优劣。同时我会分享在编码实现时极易出现的几个“坑”以及如何通过打印DP表来调试你的状态转移——这是攻克所有DP问题的必备技能。2. 动态规划的核心状态定义的两种视角与转移方程推导解决“最优包含”这类字符串DP问题第一步也是最关键的一步就是定义出正确的DP状态。状态定义决定了你思考问题的角度也直接影响了转移方程的复杂度和代码实现的难度。这里我介绍两种最常见、也最实用的思路。2.1 视角一直接改编自编辑距离这是最直观的一种思路。我们设dp[i][j]表示考虑字符串S的前i个字符下标从1开始和字符串T的前j个字符为了使得S的前i个字符中“包含”T的前j个字符即T的前j个字符是S前i个字符的子序列所需要的最小修改代价。状态转移方程推导我们来考虑最后一个字符即S[i]和T[j]。匹配成功如果S[i] T[j]那么最后一个字符天生就是匹配的。我们不需要对S[i]进行任何操作问题规模就缩小为dp[i-1][j-1]。即dp[i][j] dp[i-1][j-1]。匹配失败如果S[i] ! T[j]我们有两种选择选择用 S[i] 来匹配 T[j]既然不相等我们就必须修改S[i]使其等于T[j]这会产生一个修改代价通常题目中定义为1。修改后最后一个字符匹配了问题规模同样缩小为dp[i-1][j-1]。所以这种情况的代价是dp[i-1][j-1] cost_modifycost_modify通常是1。选择不用 S[i] 来匹配 T[j]我们忽略掉S[i]试图用S的前i-1个字符去包含T的前j个字符。这相当于在S中“删除”或“跳过”当前字符这个操作代价通常为0因为题目只关心包含TS中多余的字符可以免费忽略。所以这种情况的代价是dp[i-1][j]。我们需要在上述两种选择中取最小值。因此综合起来状态转移方程为如果 S[i] T[j]: dp[i][j] dp[i-1][j-1] 否则: dp[i][j] min(dp[i-1][j-1] 1, dp[i-1][j])初始化分析初始化是DP正确性的保证这里容易出错。dp[0][0]两个空字符串自然包含代价为0。dp[i][0]用S的前i个字符去包含一个空字符串T永远可以做到且不需要任何操作代价为0。所以对于所有idp[i][0] 0。dp[0][j] (j0)用一个空字符串S去包含一个非空的T这是不可能完成的任务。我们可以将其初始化为一个无穷大INF的值表示不可达。这种定义方式非常直接完美对应了编辑距离中只使用“修改”和“删除S中的字符”操作的情况。代码写起来也简洁。2.2 视角二基于子序列匹配的经典DP模型第二种视角更侧重于“子序列”匹配本身。我们定义dp[i][j]表示字符串S的前i个字符中至少需要修改多少个字符才能使其拥有一个以第i个字符结尾的、且与T的前j个字符完全匹配的子序列。这个定义稍微有点绕但威力巨大。它强调的是“以S[i]结尾”。这样定义的好处是当我们最终计算答案时答案不是dp[lenS][lenT]而是min(dp[i][lenT])其中i从1到lenS。因为T可以被包含在S的任意位置结束。状态转移方程推导对于dp[i][j]我们同样考虑S[i]和T[j]。如果我们要让匹配的子序列以S[i]结尾并且匹配到T[j]那么S[i]必须和T[j]匹配要么相等要么修改。如果S[i] T[j]那么修改代价为0我们只需要在前i-1个字符中找到一个子序列匹配到T[j-1]即可也就是dp[i-1][j-1]。如果S[i] ! T[j]那么我们必须修改S[i]代价为1然后同样去找dp[i-1][j-1]。因此当S[i]参与匹配时代价为dp[i-1][j-1] (S[i] ! T[j] ? 1 : 0)。但是dp[i][j]的定义是“以 S[i] 结尾”如果S[i]根本不参与这次匹配呢那这个状态就是无效的或者说我们不应该从dp[i-1][j]转移过来因为dp[i-1][j]表示的是以S[i-1]结尾的情况与S[i]无关。所以在这种定义下转移来源只有dp[i-1][j-1]。然而这样会有一个问题对于dp[i][1]即匹配T的第一个字符如果S[i]不匹配T[1]我们可能希望通过修改S[i]来实现这对应上面的情况1。但如果S[i]匹配了T[1]这应该是可行的且代价为0或1。但我们的转移需要dp[i-1][0]。这就引出了初始化的关键。初始化分析dp[i][1]匹配T的第一个字符。如果S[i] T[1]代价为0否则代价为1修改S[i]。这可以作为我们初始化dp[i][1]的依据。更一般地我们可以这样初始化dp[0][j] INF(j0)dp[i][0] 0不仔细想想dp[i][0]表示“以S[i]结尾匹配T的前0个字符”这没有意义通常也设为0表示一个空匹配。但更重要的是我们需要一个起始状态。 实际上更常见的写法是我们让i和j都从1开始循环然后单独处理j1的情况for i from 1 to lenS: dp[i][1] (S[i] T[1] ? 0 : 1); // 同时dp[i][1] 也可以从 dp[i-1][1] 转移吗不能因为定义要求以S[i]结尾。 // 但我们可以让 dp[i][1] min(dp[i][1], dp[i-1][0] cost)这里dp[i-1][0]通常是0。 // 所以更简洁的初始化就是上面那句。然后对于j 1状态转移为if (j 1) { dp[i][1] (S[i] T[1]) ? 0 : 1; } else { if (i j) dp[i][j] INF; // S的前i个字符不可能包含长度为j的子序列 else { int cost (S[i] T[j]) ? 0 : 1; dp[i][j] dp[i-1][j-1] cost; // 注意这里没有 dp[i-1][j] 的转移项 } }最终答案ans min(dp[i][lenT])其中i从lenT到lenS。两种视角的对比与选择视角一编辑距离改编更通用思维负担小初始化简单代码易于编写和调试。视角二以i结尾更符合部分题目对“结束位置”有要求的变体但初始化稍复杂且最终答案需要遍历查找。对于经典的“最优包含”问题我强烈推荐使用视角一。它逻辑清晰不易出错并且在时间复杂度上都是 O(n*m)完全足够。视角二可以作为理解DP状态灵活性的一个进阶思考。3. 代码实现与细节从方程到AC的关键步骤理论分析完毕我们动手实现。这里以视角一为例给出完整的C代码框架并逐一讲解每一个细节和易错点。#include iostream #include string #include vector #include algorithm #include climits // 用于INT_MAX using namespace std; int main() { string S, T; cin S T; int lenS S.length(), lenT T.length(); // 为了方便下标从1开始我们在字符串前补一个空格 S S; T T; // 定义dp数组初始化为最大值 vectorvectorint dp(lenS 1, vectorint(lenT 1, INT_MAX / 2)); // 防止加法溢出 // 初始化 for (int i 0; i lenS; i) { dp[i][0] 0; // S的前i个字符包含空串代价为0 } for (int j 1; j lenT; j) { dp[0][j] INT_MAX / 2; // 空串S无法包含非空T设为无穷大 } // dp[0][0] 已经在上述循环中设置为0 // 状态转移 for (int i 1; i lenS; i) { for (int j 1; j lenT; j) { if (S[i] T[j]) { // 字符相等直接匹配代价继承自dp[i-1][j-1] dp[i][j] dp[i-1][j-1]; } else { // 字符不等有两种选择 // 1. 修改S[i]使其等于T[j]代价为 dp[i-1][j-1] 1 // 2. 忽略S[i]用S的前i-1个字符去匹配T的前j个字符代价为 dp[i-1][j] dp[i][j] min(dp[i-1][j-1] 1, dp[i-1][j]); } // 实际上当S[i]T[j]时dp[i-1][j]也可能更小但根据我们的定义和方程此时dp[i-1][j-1]一定不大于dp[i-1][j]吗 // 不一定考虑Sab, Ta。dp[2][1]S[2]b ! T[1]a会走到else分支。 // 但如果我们错误地在if分支里也写 dp[i][j] min(dp[i-1][j-1], dp[i-1][j])就会出错。 // 所以必须严格遵循转移方程。 } } // 最终答案dp[lenS][lenT] 表示用整个S去包含整个T的最小代价 cout dp[lenS][lenT] endl; return 0; }几个至关重要的细节下标从1开始在字符串DP中让下标从1开始可以极大地简化边界条件dp[0][j]和dp[i][0]的处理。常见的做法是在原字符串前添加一个占位符如空格。INF 的设置dp[0][j] (j0)代表不可能的状态需要用一个很大的数表示。不能使用INT_MAX因为在状态转移中可能会进行dp[i-1][j-1] 1这样的加法操作导致整数溢出变成负数。通常取INT_MAX / 2或一个比最大可能答案大得多的数如1e9。初始化顺序务必确保在状态转移时所依赖的子状态如dp[i-1][j-1]、dp[i-1][j]已经被正确计算。我们的双重循环i从1到lenSj从1到lenT是典型的自底向上填表顺序可以保证这一点。答案的位置根据我们的状态定义dp[i][j]表示用S的前i个字符去包含T的前j个字符那么最终的答案自然就是dp[lenS][lenT]。这非常直观。4. 调试技巧如何可视化DP表并定位错误动态规划代码写出来如果结果不对最有效的调试方法不是干瞪眼也不是疯狂加cout而是打印出整个DP表。通过观察表中每个格子的值是否符合你的预期你能快速定位是状态定义、转移方程还是初始化出了问题。以下是在上述代码中添加的简易调试打印函数void printDPTable(const vectorvectorint dp, const string S, const string T) { int n dp.size() - 1, m dp[0].size() - 1; cout DP Table (row:i-S, col:j-T): endl; cout ; for (int j 0; j m; j) cout T[j] ; cout endl; for (int i 0; i n; i) { cout S[i] ; for (int j 0; j m; j) { if (dp[i][j] 1e9) cout INF ; // 处理无穷大显示 else cout dp[i][j] ; } cout endl; } }在状态转移循环结束后调用printDPTable(dp, S, T)。如何分析DP表假设 S “abcdef” T “ace”。看初始化行和列第0行i0除了dp[0][0]0其他都应该是INF。第0列j0全部应该是0。检查这里就能排除初始化错误。看简单情况dp[1][1]对应 S[1]‘a’ 和 T[1]‘a’。相等所以值应为dp[0][0] 0。检查是否正确。追踪一个转移例如dp[3][2]即 S”abc”, T”ac”。S[3]‘c’, T[2]‘c’相等所以dp[3][2] dp[2][1]。而dp[2][1]是 S”ab”, T”a”。S[2]‘b’ ! ‘a’所以dp[2][1] min(dp[1][0]1, dp[1][1])。dp[1][0]0所以dp[1][0]11。dp[1][1]0。取min为0。因此dp[3][2]应为0。通过表格验证。看最终答案dp[6][3]应该是一个较小的数字这个例子中可能是0因为”ace”本就是”abcdef”的子序列。通过这种手动“演算”并对比表格输出任何错误的转移都会无所遁形。这是我调试所有DP问题的首选方法百试百灵。5. 常见变种与陷阱题目不会一成不变掌握了基础模型我们来看看“最优包含”可能怎么变以及如何应对。变种1操作代价不同基础模型中修改一个字符的代价是1。如果题目规定将字符a修改为b的代价是w(a, b)那么转移方程中dp[i-1][j-1] 1就需要改为dp[i-1][j-1] w(S[i], T[j])。你需要在读入数据后预先处理好这个代价矩阵。变种2允许插入和删除但代价不同这更接近完整的编辑距离了。状态定义可以不变但转移方程需要增加来源插入在S中插入一个字符来匹配T[j]代价为cost_insert状态从dp[i][j-1]转移。删除删除S[i]即跳过它代价为cost_delete状态从dp[i-1][j]转移。修改/匹配同上。 方程变为dp[i][j] min(dp[i-1][j-1] cost_replace, dp[i][j-1] cost_insert, dp[i-1][j] cost_delete)其中cost_replace在字符相等时为0否则为w(S[i], T[j])。变种3求具体操作方案不仅要求最小代价还要输出是如何操作的。这就需要我们在DP过程中记录“决策路径”。通常用另一个数组pre[i][j]记录到达状态(i,j)时所做的最后一个操作0-匹配1-修改2-插入3-删除。在计算完DP表后从终点(lenS, lenT)根据pre数组倒推回起点即可得到逆序的操作序列。陷阱内存限制与滚动数组优化如果字符串长度达到10^4级别开一个10000 x 10000的二维int数组约400MB会超出内存限制。观察状态转移方程dp[i][j]只依赖于dp[i-1][...]即上一行。因此我们可以使用滚动数组优化只保留两行当前行和上一行将空间复杂度从 O(n*m) 降为 O(m)。vectorvectorint dp(2, vectorint(lenT 1, INT_MAX / 2)); int now 0, prev 1; // 初始化第0行prev行 for (int j0; jlenT; j) dp[prev][j] (j0 ? 0 : INF); for (int i 1; i lenS; i) { // 初始化当前行now行的第0列 dp[now][0] 0; for (int j 1; j lenT; j) { if (S[i] T[j]) { dp[now][j] dp[prev][j-1]; } else { dp[now][j] min(dp[prev][j-1] 1, dp[prev][j]); } } swap(now, prev); // 交换角色当前行变为下一轮的“上一行” } // 最终答案在 dp[prev][lenT] 中因为最后交换了一次 cout dp[prev][lenT] endl;陷阱字符串读入与下标这是最基础的但也最容易导致WA错误答案的点。务必确认题目输入的字符串是否包含空格是整行读取还是单词读取下标是从0开始还是1开始在竞赛中我习惯用getline(cin, str)读取可能含空格的串用cin str读取无空格串并在处理前统一转化为下标从1开始。6. 从理论到实战一道模拟题的精讲光说不练假把式。我们找一道具体的题目来完整走一遍流程。假设题目描述如下问题描述给定两个字符串A和B我们可以对A中的任意字符进行修改每次修改可以将一个字符变成任意小写字母目标是使得B成为A的一个子序列。请问最少需要修改多少次输入格式两行每行一个字符串分别表示A和B。|A|, |B| 1000。输出格式一个整数表示最少修改次数。我们的解答思路模型识别这就是标准的“最优包含”问题只允许“修改”操作且每次修改代价为1。忽略A中字符即不用于匹配B的代价为0。状态定义采用视角一。dp[i][j]A前i个字符包含B前j个字符的最小修改次数。转移方程如果 A[i] B[j]: dp[i][j] dp[i-1][j-1] 否则: dp[i][j] min(dp[i-1][j-1] 1, dp[i-1][j])初始化dp[i][0] 0, for all i dp[0][j] INF (j0), dp[0][0]0答案dp[lenA][lenB]实现与测试输入A“abcdefgh”, B“aceg”预期输出0 因为B已经是A的子序列输入A“abcdxefgh”, B“aceg”预期输出1 需要将‘x’修改为‘c’或跳过‘x’但跳过可能更优我们计算一下手动模拟或代码运行验证。通过这样一道题我们把前面的所有知识串联了起来。在竞赛中看到“修改字符串使其包含另一个字符串”这类描述并且求最小操作次数“最优包含”的DP模型应该立刻成为你的第一反应。7. 举一反三编辑距离家族的其他成员“最优包含”只是编辑距离庞大应用家族中的一个成员。理解它们之间的联系能帮你构建起知识网络。标准编辑距离Levenshtein Distance允许增、删、改三种操作求字符串A到B的最小代价。这是所有变体的基础。最长公共子序列LCS只允许“匹配”和“跳过”删除不允许修改。其DP定义dp[i][j]表示A前i位和B前j位的LCS长度。转移方程if(A[i]B[j]) dp[i][j]dp[i-1][j-1]1 else dp[i][j]max(dp[i-1][j], dp[i][j-1])。可以看到它和“最优包含”在“跳过”操作上是相似的但目标从“最小代价”变成了“最大长度”。子串匹配问题例如“带通配符的字符串匹配”DP状态可能定义为dp[i][j]表示A的前i位是否能匹配B的前j位转移涉及通配符‘?’和‘*’的处理。DNA序列比对这是编辑距离在生物信息学的直接应用不同的插入、删除、替换修改可能具有不同的生物学意义和代价。它们的核心思想都是一致的定义出描述问题进展的状态然后思考如何从已知的、规模更小的子问题状态通过一步操作转移到当前状态。多练习、多对比、多思考状态定义的含义是掌握动态规划的不二法门。回到“最优包含”本身它之所以在蓝桥杯国赛这样的场合出现就是因为它完美地考察了选手对经典模型的理解深度和迁移能力。它告诉你算法竞赛不是背题而是掌握核心思想以不变应万变。下次再遇到它或者它的任何变体希望你能自信地拿出笔开始定义你的dp[i][j]。