1. 问题引入与核心价值最近在复盘蓝桥杯历届真题特别是国赛的题目发现2019年第十届软件类国赛C/CB组的这道“最优包含”题非常有意思。它初看像一道简单的字符串编辑题但仔细琢磨其内核是一个经典的动态规划问题并且存在不小的优化空间。很多同学在练习时可能只满足于写出一个能通过样例的DP解法却忽略了题目背后对算法复杂度的严苛要求以及从“正确解”到“高效解”的思维跃迁。这道题恰好是一个绝佳的样本能让我们深入理解动态规划的状态设计、转移方程以及如何通过观察问题性质进行时间或空间上的优化。简单来说“最优包含”问题可以这样描述我们有两个字符串S和T我们可以对字符串S进行一系列操作每次操作可以修改S中的一个字符为任意小写字母。我们的目标是通过最少的修改次数使得字符串T成为字符串S的一个子序列。注意这里是子序列而不是子串。这意味着T中的字符在S中可以不连续出现但必须保持原有的相对顺序。举个例子如果S是“abcde”T是“ace”那么T本身就是S的一个子序列无需任何修改。但如果S是“abxde”T是“ace”那么我们需要将S中的‘x’修改为‘c’这样修改后的S字符串“abcde”就包含了子序列“ace”总共进行了1次修改。这个问题在生物信息学的序列比对、文本差异分析等领域有实际的应用背景。比如在基因序列分析中我们可能想知道将一个DNA序列稍作修改使其包含另一个特定功能片段作为子序列最少需要改变多少个碱基。理解并高效解决这类问题是算法能力的一个重要体现。接下来我将从最朴素的动态规划思路开始一步步拆解直到介绍一种能够有效处理更长字符串的优化方法并分享我在实现过程中踩过的坑和调试心得。2. 动态规划基础模型构建面对“最优包含”问题我们首先要建立数学模型。最直接的思路就是动态规划。动态规划的核心在于定义状态和状态转移方程。对于两个字符串的问题一个非常经典的DP状态定义是dp[i][j]。2.1 状态定义与初始化我们定义dp[i][j]表示考虑字符串S的前i个字符S[1...i]和字符串T的前j个字符T[1...j]为了使得T[1...j]成为S[1...i]的一个子序列所需要的最少修改次数。这里我们假设字符串下标从1开始方便叙述。这个状态定义清晰地刻画了问题的子结构。最终我们要求解的目标就是dp[n][m]其中n是S的长度m是T的长度。接下来是初始化这是确保DP正确起点的关键当 j 0 时T是一个空字符串。空字符串是任何字符串的子序列且不需要任何修改。因此对于任意的i从0到ndp[i][0] 0。当 i 0 且 j 0 时S是一个空字符串而T不是空串。一个非空字符串不可能是一个空字符串的子序列。这是一个不可能完成的任务。在DP中我们通常用一个很大的数比如无穷大INF来表示这种不可行状态。因此dp[0][j] INF(对于 j 0)。注意在实际代码中INF可以取一个比最大可能操作数即m大的值例如0x3f3f3f3f这是一个在算法竞赛中常用的“无穷大”常量其值约为10^9并且两个0x3f3f3f3f相加不会溢出int范围。2.2 状态转移方程推导现在考虑一般情况如何从已知的小规模状态推导出dp[i][j]。我们关注S的第i个字符S[i]和T的第j个字符T[j]。对于dp[i][j]我们有两种决策不使用 S[i] 来匹配 T[j]。这意味着我们试图在 S[1...i-1] 中就已经包含了 T[1...j]。那么此时的状态值直接继承自dp[i-1][j]。使用 S[i] 来匹配 T[j]。这要求 S[i] 最终必须等于 T[j]才能让 T[j] 成为子序列的一部分。但当前 S[i] 可能不等于 T[j]。如果S[i] T[j]那么我们不需要修改 S[i]可以直接用它来匹配。此时我们需要看 S[1...i-1] 是否包含了 T[1...j-1]即状态值来自dp[i-1][j-1]。如果S[i] ! T[j]那么我们必须修改 S[i] 使其等于 T[j]这需要花费1次修改操作。修改之后再用它来匹配 T[j]。此时状态值来自dp[i-1][j-1] 1。我们的目标是最小化修改次数所以dp[i][j]应该取上述两种决策中的最小值。因此状态转移方程可以写为如果 S[i] T[j]: dp[i][j] min(dp[i-1][j], dp[i-1][j-1]) 否则 (S[i] ! T[j]): dp[i][j] min(dp[i-1][j], dp[i-1][j-1] 1)这个方程非常直观地体现了动态规划的“最优子结构”特性。2.3 基础DP代码实现与复杂度分析根据上述分析我们可以写出最基础的动态规划代码。这里使用C为例并假设字符串已经读入下标从0开始但在DP数组中我们使用下标1~n和1~m来对应字符串的字符以简化边界处理。#include iostream #include cstring #include algorithm using namespace std; const int N 1010; // 假设最大长度根据题目调整 const int INF 0x3f3f3f3f; char S[N], T[N]; int dp[N][N]; int main() { scanf(%s%s, S 1, T 1); // 从下标1开始存储 int n strlen(S 1); int m strlen(T 1); // 初始化 for (int i 0; i n; i) dp[i][0] 0; // T为空串 for (int j 1; j m; j) dp[0][j] INF; // S为空串T非空 // DP过程 for (int i 1; i n; i) { for (int j 1; j m; j) { if (S[i] T[j]) { dp[i][j] min(dp[i-1][j], dp[i-1][j-1]); } else { dp[i][j] min(dp[i-1][j], dp[i-1][j-1] 1); } } } printf(%d\n, dp[n][m]); return 0; }时间复杂度分析代码中有两层循环分别遍历S的长度n和T的长度m因此时间复杂度为O(n * m)。空间复杂度分析我们使用了一个(n1) * (m1)的二维数组dp空间复杂度为O(n * m)。对于蓝桥杯国赛的题目n和m的范围通常是1000左右那么n*m ≈ 10^6这个计算量在普通计算机上是可以接受的大约千万次运算。但是如果字符串长度达到5000甚至10000n*m就会达到2500万到1亿虽然可能仍在时间限制内但空间开销dp[10000][10000]是4亿字节约381MB很可能超出内存限制。因此这个基础DP解法存在优化空间。3. 空间复杂度优化滚动数组观察上面的状态转移方程你会发现在计算dp[i][j]时它只依赖于上一行i-1的数据dp[i-1][j]和dp[i-1][j-1]。它既不依赖同一行的其他列也不依赖更早的行。这是一个非常明显的可以使用滚动数组进行空间优化的信号。滚动数组的思想是既然我们只需要上一行的数据来计算当前行那么我们就不需要保留整个n*m的矩阵只需要两个一维数组一个代表“上一行”prev一个代表“当前行”curr在计算完当前行后将当前行赋值给“上一行”用于下一轮计算。但这里有一个关键细节在计算curr[j]时我们需要prev[j](即上一行的同一列) 和prev[j-1](即上一行的前一列)。如果我们从左到右顺序计算curr数组当计算到curr[j]时curr[j-1]已经被当前行的新值覆盖了而我们需要的是上一行的prev[j-1]。因此我们必须从右向左遍历j这样在计算curr[j]时curr[j-1]还是旧值即我们不需要的而prev[j-1]依然完好无损。优化后的空间复杂度为O(m)即只与较短的字符串T的长度相关。这对于处理长字符串非常有利。#include iostream #include cstring #include algorithm using namespace std; const int N 1010; const int INF 0x3f3f3f3f; char S[N], T[N]; int dp[N]; // dp[j] 相当于当前行的 curr[j] int main() { scanf(%s%s, S 1, T 1); int n strlen(S 1); int m strlen(T 1); // 初始化相当于dp[0][j]即S为空串时 for (int j 0; j m; j) { dp[j] INF; } dp[0] 0; // dp[i][0] 0但我们的dp数组只存一行所以dp[0]始终为0 // DP过程使用滚动数组内层循环从右向左 for (int i 1; i n; i) { // 为了获取上一行的dp[j-1]我们必须从右向左更新 for (int j m; j 1; j--) { if (S[i] T[j]) { dp[j] min(dp[j], dp[j-1]); // dp[j]是上一行的值dp[j-1]是上一行的值 } else { dp[j] min(dp[j], dp[j-1] 1); } } // 注意dp[0] 永远为0不需要更新 } printf(%d\n, dp[m]); return 0; }实操心得滚动数组优化时内层循环的遍历方向是极易出错的地方。一定要根据状态转移的依赖关系来确定方向。像本题这样依赖“上一行”的“当前列”和“前一列”就必须逆序更新。如果依赖的是“当前行”的“前一列”则通常需要顺序更新。画一个简单的二维表格标出依赖关系是避免出错的好方法。4. 时间复杂度优化利用问题性质空间优化后时间复杂度仍然是 O(n*m)。在某些极端情况下比如n和m都很大我们还能不能优化呢仔细分析问题我们可以发现一个性质修改操作的目标是让T成为S的子序列而子序列不要求连续。这意味着对于S中的每个字符我们有两种选择用它去匹配T中的某个字符或者跳过它。一个更高效的思路是直接遍历S同时维护一个指针指向T中当前待匹配的字符。如果S的当前字符等于T的待匹配字符则匹配成功指针后移否则我们可以选择修改它花费1使其匹配或者直接跳过它花费0。但这听起来像贪心而贪心可能得不到最优解。例如 S“ab”, T“ba”。贪心从S开始找‘b’第一个字符‘a’不匹配如果选择修改‘a’为‘b’花费1然后S的第二个字符‘b’匹配T的第二个字符‘a’需要再修改一次总花费2。但实际上最优解是跳过S的‘a’用S的‘b’匹配T的‘b’花费0然后修改S的‘a’或某个虚拟位置为‘a’来匹配T的‘a’花费1总花费1。所以简单的贪心不行。然而我们可以换一种DP状态定义利用“编辑距离”类问题的思想但结合子序列的特性。定义dp[j]表示匹配到T的第j个字符所需的最少修改次数这个定义和滚动数组优化后的含义一致。当我们顺序扫描S的每个字符S[i]时我们可以尝试用它去更新所有可能的状态dp[j]。但这里有一个更巧妙的优化视角对于固定的i当S[i]匹配T[j]时状态转移是dp[j] min(dp[j], dp[j-1])当不匹配时是dp[j] min(dp[j], dp[j-1]1)。我们发现对于每个idp数组的更新实际上是在尝试用S[i]去“松弛”所有以T[j]结尾的子序列匹配代价。这个过程和用S中的字符去“覆盖”T中的字符很像。实际上存在一种时间复杂度为O(n m * |Σ|)的优化方法其中 |Σ| 是字符集大小本题为26。思路是预处理出T字符串中每个位置j的下一个字符c出现的位置nextPos[j][c]。这样在DP时对于S中的字符S[i]我们可以快速知道它能够更新T的哪些位置从而避免内层的m次循环。但这种优化在本题n和m为1000量级时带来的提升并不明显且代码更复杂。对于蓝桥杯赛场掌握滚动数组优化通常已经足够。5. 边界处理与调试技巧实录即使思路清晰在实现时也常常会遇到各种边界问题。下面记录几个我调试时遇到的典型问题和解决方法。5.1 初始化陷阱在基础DP中初始化dp[0][j] INF至关重要。我曾忘记初始化j0的情况导致结果错误。因为如果默认初始化为0程序会认为空字符串S可以零成本包含非空T这显然不对。在滚动数组版本中初始化dp[j] INF (j0)和dp[0]0同样关键。并且在每一轮i的循环开始时dp数组存储的就是“上一行”的值我们直接在其基础上更新。5.2 下标与循环范围字符串从1开始索引可以避免很多边界判断。dp数组的大小应至少为[N][M]其中Nn1, Mm1。循环时i从1到nj从1到m。务必确保数组不会越界。在滚动数组版本中内层循环for (int j m; j 1; j--)的逆序是灵魂。如果写成了顺序dp[j-1]在计算dp[j]时已经被当前行的新值覆盖结果会完全错误。调试时可以用一个极小的样例如S”a”, T”b”单步跟踪观察dp数组的变化。5.3 INF 值的选择INF要足够大大于任何可能的最优解但又不能太大导致加法溢出。0x3f3f3f3f是一个很好的选择其十进制是1061109567约10^9。在本题中最大修改次数不会超过T的长度m最坏情况把S全改一遍所以0x3f3f3f3f是安全的。使用min函数时INF不会被误选为最小值。5.4 测试用例设计自己设计测试用例是验证程序正确性的好习惯。简单用例S”abc”, T”abc”结果应为0。包含用例S”abcd”, T”acd”结果应为0已是子序列。需要修改用例S”abxd”, T”acd”结果应为1改’x’为’c’。全修改用例S”aaaa”, T”bbbb”结果应为4。空串用例T为空串结果应为0S为空串T非空结果应为INF或根据题目要求输出特定值。长串用例生成随机字符串用暴力搜索适用于很小规模或对拍来验证DP结果的正确性。6. 代码最终版本与性能对比综合以上分析给出一个经过滚动数组优化的稳健版本并附上注释。#include iostream #include cstring #include algorithm using namespace std; const int MAXM 1010; // T的最大长度 const int INF 0x3f3f3f3f; int main() { char S[MAXM * 2], T[MAXM]; // S可以更长适当开大 int dp[MAXM]; // dp[j]: 匹配到T前j个字符所需最小修改次数 scanf(%s%s, S 1, T 1); // 从索引1开始读入 int n strlen(S 1); int m strlen(T 1); // 初始化匹配0个字符不需要修改匹配j(0)个字符初始为无穷大 for (int j 1; j m; j) dp[j] INF; dp[0] 0; // 动态规划i遍历S的每个字符 for (int i 1; i n; i) { // 必须从后向前更新因为dp[j]依赖于dp[j-1]上一行的值 for (int j m; j 1; j--) { if (S[i] T[j]) { // 字符相等可以选择不匹配继承dp[j]或匹配继承dp[j-1] dp[j] min(dp[j], dp[j-1]); } else { // 字符不等可以选择不匹配继承dp[j]或修改后匹配dp[j-1]1 dp[j] min(dp[j], dp[j-1] 1); } } // dp[0]始终为0无需更新 } // 输出结果dp[m]可能为INF表示无法实现根据题目通常保证有解 printf(%d\n, dp[m]); return 0; }性能对比基础DP时间复杂度 O(nm)空间复杂度 O(nm)。n,m1000时空间约4MB。滚动数组DP时间复杂度 O(n*m)空间复杂度 O(m)。n,m1000时空间约4KB。 在时间相同的情况下空间消耗降低到了原来的约1/1000极大地提升了算法应对更大数据规模的能力也符合竞赛中对空间效率的考察要求。7. 举一反三与思维拓展解决“最优包含”问题不仅仅是学会了一道题更是掌握了一类问题的解法。它的DP模型与经典的“编辑距离”问题非常相似只是操作限制为“修改”和“跳过”对应编辑距离的“替换”和“删除”并且目标不是完全相等而是子序列包含。你可以尝试思考以下变种问题来巩固和拓展这种DP思维操作代价变化如果修改不同字符的代价不同比如元音字母互改代价小辅音字母互改代价大如何调整状态转移方程答案在dp[i-1][j-1] cost(S[i], T[j])处将固定的1改为可变代价允许插入和删除除了修改S中的字符还允许在S中插入字符或在T中删除字符代价均为1使得T成为S的子序列求最小总代价。这就更接近编辑距离问题了。求具体方案不仅要求出最小修改次数还要输出一种具体的修改方案。这需要在DP过程中记录状态转移的路径来自哪个前驱状态最后从dp[n][m]反向回溯即可。这道“最优包含”题从最直观的二维DP到空间优化的滚动数组体现了算法竞赛中“先求正确再求高效”的典型解题路径。理解状态定义的物理意义严谨推导转移方程细心处理边界条件最后根据数据特征进行优化这套流程适用于绝大多数动态规划问题。在平时练习时不妨多问自己几个“为什么”为什么状态要这么定义为什么转移方程是这样还有没有更好的定义方法多进行这样的思考算法能力才能真正得到提升。 动态规划解字符串最优包含问题：从基础模型到滚动数组优化
1. 问题引入与核心价值最近在复盘蓝桥杯历届真题特别是国赛的题目发现2019年第十届软件类国赛C/CB组的这道“最优包含”题非常有意思。它初看像一道简单的字符串编辑题但仔细琢磨其内核是一个经典的动态规划问题并且存在不小的优化空间。很多同学在练习时可能只满足于写出一个能通过样例的DP解法却忽略了题目背后对算法复杂度的严苛要求以及从“正确解”到“高效解”的思维跃迁。这道题恰好是一个绝佳的样本能让我们深入理解动态规划的状态设计、转移方程以及如何通过观察问题性质进行时间或空间上的优化。简单来说“最优包含”问题可以这样描述我们有两个字符串S和T我们可以对字符串S进行一系列操作每次操作可以修改S中的一个字符为任意小写字母。我们的目标是通过最少的修改次数使得字符串T成为字符串S的一个子序列。注意这里是子序列而不是子串。这意味着T中的字符在S中可以不连续出现但必须保持原有的相对顺序。举个例子如果S是“abcde”T是“ace”那么T本身就是S的一个子序列无需任何修改。但如果S是“abxde”T是“ace”那么我们需要将S中的‘x’修改为‘c’这样修改后的S字符串“abcde”就包含了子序列“ace”总共进行了1次修改。这个问题在生物信息学的序列比对、文本差异分析等领域有实际的应用背景。比如在基因序列分析中我们可能想知道将一个DNA序列稍作修改使其包含另一个特定功能片段作为子序列最少需要改变多少个碱基。理解并高效解决这类问题是算法能力的一个重要体现。接下来我将从最朴素的动态规划思路开始一步步拆解直到介绍一种能够有效处理更长字符串的优化方法并分享我在实现过程中踩过的坑和调试心得。2. 动态规划基础模型构建面对“最优包含”问题我们首先要建立数学模型。最直接的思路就是动态规划。动态规划的核心在于定义状态和状态转移方程。对于两个字符串的问题一个非常经典的DP状态定义是dp[i][j]。2.1 状态定义与初始化我们定义dp[i][j]表示考虑字符串S的前i个字符S[1...i]和字符串T的前j个字符T[1...j]为了使得T[1...j]成为S[1...i]的一个子序列所需要的最少修改次数。这里我们假设字符串下标从1开始方便叙述。这个状态定义清晰地刻画了问题的子结构。最终我们要求解的目标就是dp[n][m]其中n是S的长度m是T的长度。接下来是初始化这是确保DP正确起点的关键当 j 0 时T是一个空字符串。空字符串是任何字符串的子序列且不需要任何修改。因此对于任意的i从0到ndp[i][0] 0。当 i 0 且 j 0 时S是一个空字符串而T不是空串。一个非空字符串不可能是一个空字符串的子序列。这是一个不可能完成的任务。在DP中我们通常用一个很大的数比如无穷大INF来表示这种不可行状态。因此dp[0][j] INF(对于 j 0)。注意在实际代码中INF可以取一个比最大可能操作数即m大的值例如0x3f3f3f3f这是一个在算法竞赛中常用的“无穷大”常量其值约为10^9并且两个0x3f3f3f3f相加不会溢出int范围。2.2 状态转移方程推导现在考虑一般情况如何从已知的小规模状态推导出dp[i][j]。我们关注S的第i个字符S[i]和T的第j个字符T[j]。对于dp[i][j]我们有两种决策不使用 S[i] 来匹配 T[j]。这意味着我们试图在 S[1...i-1] 中就已经包含了 T[1...j]。那么此时的状态值直接继承自dp[i-1][j]。使用 S[i] 来匹配 T[j]。这要求 S[i] 最终必须等于 T[j]才能让 T[j] 成为子序列的一部分。但当前 S[i] 可能不等于 T[j]。如果S[i] T[j]那么我们不需要修改 S[i]可以直接用它来匹配。此时我们需要看 S[1...i-1] 是否包含了 T[1...j-1]即状态值来自dp[i-1][j-1]。如果S[i] ! T[j]那么我们必须修改 S[i] 使其等于 T[j]这需要花费1次修改操作。修改之后再用它来匹配 T[j]。此时状态值来自dp[i-1][j-1] 1。我们的目标是最小化修改次数所以dp[i][j]应该取上述两种决策中的最小值。因此状态转移方程可以写为如果 S[i] T[j]: dp[i][j] min(dp[i-1][j], dp[i-1][j-1]) 否则 (S[i] ! T[j]): dp[i][j] min(dp[i-1][j], dp[i-1][j-1] 1)这个方程非常直观地体现了动态规划的“最优子结构”特性。2.3 基础DP代码实现与复杂度分析根据上述分析我们可以写出最基础的动态规划代码。这里使用C为例并假设字符串已经读入下标从0开始但在DP数组中我们使用下标1~n和1~m来对应字符串的字符以简化边界处理。#include iostream #include cstring #include algorithm using namespace std; const int N 1010; // 假设最大长度根据题目调整 const int INF 0x3f3f3f3f; char S[N], T[N]; int dp[N][N]; int main() { scanf(%s%s, S 1, T 1); // 从下标1开始存储 int n strlen(S 1); int m strlen(T 1); // 初始化 for (int i 0; i n; i) dp[i][0] 0; // T为空串 for (int j 1; j m; j) dp[0][j] INF; // S为空串T非空 // DP过程 for (int i 1; i n; i) { for (int j 1; j m; j) { if (S[i] T[j]) { dp[i][j] min(dp[i-1][j], dp[i-1][j-1]); } else { dp[i][j] min(dp[i-1][j], dp[i-1][j-1] 1); } } } printf(%d\n, dp[n][m]); return 0; }时间复杂度分析代码中有两层循环分别遍历S的长度n和T的长度m因此时间复杂度为O(n * m)。空间复杂度分析我们使用了一个(n1) * (m1)的二维数组dp空间复杂度为O(n * m)。对于蓝桥杯国赛的题目n和m的范围通常是1000左右那么n*m ≈ 10^6这个计算量在普通计算机上是可以接受的大约千万次运算。但是如果字符串长度达到5000甚至10000n*m就会达到2500万到1亿虽然可能仍在时间限制内但空间开销dp[10000][10000]是4亿字节约381MB很可能超出内存限制。因此这个基础DP解法存在优化空间。3. 空间复杂度优化滚动数组观察上面的状态转移方程你会发现在计算dp[i][j]时它只依赖于上一行i-1的数据dp[i-1][j]和dp[i-1][j-1]。它既不依赖同一行的其他列也不依赖更早的行。这是一个非常明显的可以使用滚动数组进行空间优化的信号。滚动数组的思想是既然我们只需要上一行的数据来计算当前行那么我们就不需要保留整个n*m的矩阵只需要两个一维数组一个代表“上一行”prev一个代表“当前行”curr在计算完当前行后将当前行赋值给“上一行”用于下一轮计算。但这里有一个关键细节在计算curr[j]时我们需要prev[j](即上一行的同一列) 和prev[j-1](即上一行的前一列)。如果我们从左到右顺序计算curr数组当计算到curr[j]时curr[j-1]已经被当前行的新值覆盖了而我们需要的是上一行的prev[j-1]。因此我们必须从右向左遍历j这样在计算curr[j]时curr[j-1]还是旧值即我们不需要的而prev[j-1]依然完好无损。优化后的空间复杂度为O(m)即只与较短的字符串T的长度相关。这对于处理长字符串非常有利。#include iostream #include cstring #include algorithm using namespace std; const int N 1010; const int INF 0x3f3f3f3f; char S[N], T[N]; int dp[N]; // dp[j] 相当于当前行的 curr[j] int main() { scanf(%s%s, S 1, T 1); int n strlen(S 1); int m strlen(T 1); // 初始化相当于dp[0][j]即S为空串时 for (int j 0; j m; j) { dp[j] INF; } dp[0] 0; // dp[i][0] 0但我们的dp数组只存一行所以dp[0]始终为0 // DP过程使用滚动数组内层循环从右向左 for (int i 1; i n; i) { // 为了获取上一行的dp[j-1]我们必须从右向左更新 for (int j m; j 1; j--) { if (S[i] T[j]) { dp[j] min(dp[j], dp[j-1]); // dp[j]是上一行的值dp[j-1]是上一行的值 } else { dp[j] min(dp[j], dp[j-1] 1); } } // 注意dp[0] 永远为0不需要更新 } printf(%d\n, dp[m]); return 0; }实操心得滚动数组优化时内层循环的遍历方向是极易出错的地方。一定要根据状态转移的依赖关系来确定方向。像本题这样依赖“上一行”的“当前列”和“前一列”就必须逆序更新。如果依赖的是“当前行”的“前一列”则通常需要顺序更新。画一个简单的二维表格标出依赖关系是避免出错的好方法。4. 时间复杂度优化利用问题性质空间优化后时间复杂度仍然是 O(n*m)。在某些极端情况下比如n和m都很大我们还能不能优化呢仔细分析问题我们可以发现一个性质修改操作的目标是让T成为S的子序列而子序列不要求连续。这意味着对于S中的每个字符我们有两种选择用它去匹配T中的某个字符或者跳过它。一个更高效的思路是直接遍历S同时维护一个指针指向T中当前待匹配的字符。如果S的当前字符等于T的待匹配字符则匹配成功指针后移否则我们可以选择修改它花费1使其匹配或者直接跳过它花费0。但这听起来像贪心而贪心可能得不到最优解。例如 S“ab”, T“ba”。贪心从S开始找‘b’第一个字符‘a’不匹配如果选择修改‘a’为‘b’花费1然后S的第二个字符‘b’匹配T的第二个字符‘a’需要再修改一次总花费2。但实际上最优解是跳过S的‘a’用S的‘b’匹配T的‘b’花费0然后修改S的‘a’或某个虚拟位置为‘a’来匹配T的‘a’花费1总花费1。所以简单的贪心不行。然而我们可以换一种DP状态定义利用“编辑距离”类问题的思想但结合子序列的特性。定义dp[j]表示匹配到T的第j个字符所需的最少修改次数这个定义和滚动数组优化后的含义一致。当我们顺序扫描S的每个字符S[i]时我们可以尝试用它去更新所有可能的状态dp[j]。但这里有一个更巧妙的优化视角对于固定的i当S[i]匹配T[j]时状态转移是dp[j] min(dp[j], dp[j-1])当不匹配时是dp[j] min(dp[j], dp[j-1]1)。我们发现对于每个idp数组的更新实际上是在尝试用S[i]去“松弛”所有以T[j]结尾的子序列匹配代价。这个过程和用S中的字符去“覆盖”T中的字符很像。实际上存在一种时间复杂度为O(n m * |Σ|)的优化方法其中 |Σ| 是字符集大小本题为26。思路是预处理出T字符串中每个位置j的下一个字符c出现的位置nextPos[j][c]。这样在DP时对于S中的字符S[i]我们可以快速知道它能够更新T的哪些位置从而避免内层的m次循环。但这种优化在本题n和m为1000量级时带来的提升并不明显且代码更复杂。对于蓝桥杯赛场掌握滚动数组优化通常已经足够。5. 边界处理与调试技巧实录即使思路清晰在实现时也常常会遇到各种边界问题。下面记录几个我调试时遇到的典型问题和解决方法。5.1 初始化陷阱在基础DP中初始化dp[0][j] INF至关重要。我曾忘记初始化j0的情况导致结果错误。因为如果默认初始化为0程序会认为空字符串S可以零成本包含非空T这显然不对。在滚动数组版本中初始化dp[j] INF (j0)和dp[0]0同样关键。并且在每一轮i的循环开始时dp数组存储的就是“上一行”的值我们直接在其基础上更新。5.2 下标与循环范围字符串从1开始索引可以避免很多边界判断。dp数组的大小应至少为[N][M]其中Nn1, Mm1。循环时i从1到nj从1到m。务必确保数组不会越界。在滚动数组版本中内层循环for (int j m; j 1; j--)的逆序是灵魂。如果写成了顺序dp[j-1]在计算dp[j]时已经被当前行的新值覆盖结果会完全错误。调试时可以用一个极小的样例如S”a”, T”b”单步跟踪观察dp数组的变化。5.3 INF 值的选择INF要足够大大于任何可能的最优解但又不能太大导致加法溢出。0x3f3f3f3f是一个很好的选择其十进制是1061109567约10^9。在本题中最大修改次数不会超过T的长度m最坏情况把S全改一遍所以0x3f3f3f3f是安全的。使用min函数时INF不会被误选为最小值。5.4 测试用例设计自己设计测试用例是验证程序正确性的好习惯。简单用例S”abc”, T”abc”结果应为0。包含用例S”abcd”, T”acd”结果应为0已是子序列。需要修改用例S”abxd”, T”acd”结果应为1改’x’为’c’。全修改用例S”aaaa”, T”bbbb”结果应为4。空串用例T为空串结果应为0S为空串T非空结果应为INF或根据题目要求输出特定值。长串用例生成随机字符串用暴力搜索适用于很小规模或对拍来验证DP结果的正确性。6. 代码最终版本与性能对比综合以上分析给出一个经过滚动数组优化的稳健版本并附上注释。#include iostream #include cstring #include algorithm using namespace std; const int MAXM 1010; // T的最大长度 const int INF 0x3f3f3f3f; int main() { char S[MAXM * 2], T[MAXM]; // S可以更长适当开大 int dp[MAXM]; // dp[j]: 匹配到T前j个字符所需最小修改次数 scanf(%s%s, S 1, T 1); // 从索引1开始读入 int n strlen(S 1); int m strlen(T 1); // 初始化匹配0个字符不需要修改匹配j(0)个字符初始为无穷大 for (int j 1; j m; j) dp[j] INF; dp[0] 0; // 动态规划i遍历S的每个字符 for (int i 1; i n; i) { // 必须从后向前更新因为dp[j]依赖于dp[j-1]上一行的值 for (int j m; j 1; j--) { if (S[i] T[j]) { // 字符相等可以选择不匹配继承dp[j]或匹配继承dp[j-1] dp[j] min(dp[j], dp[j-1]); } else { // 字符不等可以选择不匹配继承dp[j]或修改后匹配dp[j-1]1 dp[j] min(dp[j], dp[j-1] 1); } } // dp[0]始终为0无需更新 } // 输出结果dp[m]可能为INF表示无法实现根据题目通常保证有解 printf(%d\n, dp[m]); return 0; }性能对比基础DP时间复杂度 O(nm)空间复杂度 O(nm)。n,m1000时空间约4MB。滚动数组DP时间复杂度 O(n*m)空间复杂度 O(m)。n,m1000时空间约4KB。 在时间相同的情况下空间消耗降低到了原来的约1/1000极大地提升了算法应对更大数据规模的能力也符合竞赛中对空间效率的考察要求。7. 举一反三与思维拓展解决“最优包含”问题不仅仅是学会了一道题更是掌握了一类问题的解法。它的DP模型与经典的“编辑距离”问题非常相似只是操作限制为“修改”和“跳过”对应编辑距离的“替换”和“删除”并且目标不是完全相等而是子序列包含。你可以尝试思考以下变种问题来巩固和拓展这种DP思维操作代价变化如果修改不同字符的代价不同比如元音字母互改代价小辅音字母互改代价大如何调整状态转移方程答案在dp[i-1][j-1] cost(S[i], T[j])处将固定的1改为可变代价允许插入和删除除了修改S中的字符还允许在S中插入字符或在T中删除字符代价均为1使得T成为S的子序列求最小总代价。这就更接近编辑距离问题了。求具体方案不仅要求出最小修改次数还要输出一种具体的修改方案。这需要在DP过程中记录状态转移的路径来自哪个前驱状态最后从dp[n][m]反向回溯即可。这道“最优包含”题从最直观的二维DP到空间优化的滚动数组体现了算法竞赛中“先求正确再求高效”的典型解题路径。理解状态定义的物理意义严谨推导转移方程细心处理边界条件最后根据数据特征进行优化这套流程适用于绝大多数动态规划问题。在平时练习时不妨多问自己几个“为什么”为什么状态要这么定义为什么转移方程是这样还有没有更好的定义方法多进行这样的思考算法能力才能真正得到提升。