1. 从“编辑距离”到“最优包含”一个经典算法的竞赛实战如果你刷过力扣或者准备过蓝桥杯国赛那么“编辑距离”这个词你一定不陌生。它几乎是动态规划入门必学的经典例题用来衡量两个字符串的相似度。但算法竞赛的魅力就在于它不会直接考你课本上的原题而是会把经典模型藏在一个全新的问题场景后面等着你去发现和拆解。“最优包含”就是这样一个典型的例子。我第一次在蓝桥杯国赛的模拟题里遇到它时第一反应也是去套编辑距离的模板结果发现有点对不上仔细琢磨后才恍然大悟——这其实是编辑距离思想的一个精妙变种考察的是你对状态定义和转移方程本质的理解而不仅仅是背诵模板。简单来说“最优包含”问题可以这样描述给定两个字符串 S 和 T我们可以对字符串 S 进行若干次操作每次操作可以修改 S 中的一个字符为任意字符目标是使得操作后的 S 包含子序列 T。这里“包含”指的是 T 是 S 的一个子序列不要求连续但顺序必须一致。我们需要求出最少的操作次数。这听起来是不是和“通过最少的编辑操作增、删、改将 S 变为 T”的编辑距离问题有异曲同工之妙没错核心的动态规划思想是相通的但状态定义和转移逻辑需要根据“子序列包含”这个新约束进行重塑。理解这个重塑的过程比你多刷十道模板题更有价值。这篇内容我就以一个过来人的身份带你彻底拆解“最优包含”问题。我不会只给你最终的状态转移方程那样毫无意义。我会从最朴素的暴力思路开始一步步推导为什么需要动态规划如何设计状态状态之间如何转移并重点对比它与标准编辑距离的异同。最后我会分享在竞赛实战中如何快速识别这类“变种题”以及编码时有哪些一写就错的坑。无论你是正在备战蓝桥杯、ACM还是单纯想深化对动态规划的理解相信这篇都能给你带来实实在在的收获。2. 问题本质分析与思路演进2.1 问题重述与核心约束解析首先我们明确一下“最优包含”问题的形式化定义输入两个字符串 S 和 T长度分别为 n 和 m (1 m n)。操作每次操作可以将 S 中的任意一个字符修改为任意其他字符通常是小写字母。注意只能修改不能插入或删除。这是与编辑距离的第一个关键区别。目标通过对 S 进行若干次可以为0修改操作使得 T 成为操作后字符串 S 的一个子序列。输出达成目标所需的最少修改次数。这里有几个关键约束需要吃透操作唯一性只有“修改”一种操作。在编辑距离中我们通常有插入、删除、替换三种操作。而这里S 的长度 n 是固定的我们无法改变其长度只能改变其内容。这直接影响了状态转移的可能性。目标宽松性目标是 T 成为 S 的子序列而非子串。这意味着 T 的字符在 S 中可以不连续出现只要相对顺序保持一致即可。例如T“abc”那么 S“axxbxxc” 是包含 T 作为子序列的S中的第1、4、7个字符依次构成了“abc”。这个“不连续”的特性是设计状态转移方程的核心。最小化修改我们关心的是最少的修改次数而不是是否能够达成。这天然指向了最优化问题动态规划是首选工具。理解这些约束后一个最朴素的想法是枚举 S 中所有长度为 m 的子序列虽然不要求连续但我们可以考虑匹配顺序然后计算将 S 中对应位置的字符修改为 T 中字符所需的次数取最小值。然而S 中长度为 m 的子序列数量是组合数 C(n, m)当 n 和 m 达到几百时这个数量是天文数字暴力枚举完全不可行。这就迫使我们寻找更聪明的办法——动态规划。2.2 从编辑距离到最优包含思路的迁移与调整既然暴力不行我们自然想到经典的编辑距离Levenshtein Distance模型。标准编辑距离的 DP 状态dp[i][j]通常定义为将字符串 A 的前 i 个字符转换为字符串 B 的前 j 个字符所需的最少操作次数。操作包括增、删、改。如果我们生搬硬套定义dp[i][j]为“将 S 的前 i 个字符通过修改操作变成包含 T 的前 j 个字符作为子序列所需的最少操作次数”会立刻遇到问题操作不匹配编辑距离有“增”、“删”而我们这里只有“改”。如果 S[i] 不等于 T[j]在编辑距离中我们可以选择删除 S[i]dp[i-1][j] 1或者插入 T[j]dp[i][j-1] 1。但在“最优包含”里S 的长度不能变我们不能删除 S[i]也不能插入字符。我们只能选择是否用 S[i] 去匹配 T[j]。目标不匹配编辑距离的目标是完全相等而我们的目标是“包含子序列”。这意味着对于 S 的前 i 个字符我们并不需要它们完全“变成” T 的前 j 个字符而是只需要从中找到一个子序列等于 T 的前 j 个字符即可。S 中未被用于匹配的字符可以保持原样只要不影响匹配。因此我们需要重新设计状态以贴合我们唯一的“修改”操作和“子序列包含”的目标。正确的思路是我们关注的是“匹配进度”。即我们正在用 S 的前 i 个字符去尝试匹配 T 的前 j 个字符看最少需要修改多少次才能让这个匹配成功。一个更精准的状态定义是dp[i][j]表示考虑 S 的前 i 个字符要使其包含 T 的前 j 个字符作为子序列所需的最少修改次数。注意这里“包含”意味着在 S[1...i] 这个前缀中存在一个子序列等于 T[1...j]。有了这个状态我们来思考转移。当我们处理到 S[i] 和 T[j] 时我们面临一个选择是否让 S[i] 参与匹配 T[j]情况一让 S[i] 参与匹配 T[j]。这要求 S[i] 最终必须等于 T[j]。如果原本 S[i] T[j]那么我们不需要修改直接使用它代价为0。如果 S[i] ! T[j]那么我们必须修改 S[i] 为 T[j]代价为1。在做出这个选择后我们的任务就变成了用 S 的前 i-1 个字符去匹配 T 的前 j-1 个字符。因此转移为dp[i-1][j-1] cost其中cost为 0 或 1。情况二不让 S[i] 参与匹配 T[j]。这意味着我们“跳过”了 S[i]不使用它来匹配当前 T 的第 j 个字符。那么匹配 T 的前 j 个字符的任务完全由 S 的前 i-1 个字符来承担。因此转移为dp[i-1][j]。我们需要的是最少修改次数所以dp[i][j]应该取上述两种情况的最小值。此外我们还需要考虑边界条件当 j 0 时表示要匹配 T 的前 0 个字符空串。空串永远是任何字符串的子序列且不需要任何修改。所以对于任意 idp[i][0] 0。当 i 0 且 j 0 时表示用空串 S 去匹配非空的 T这是不可能的。我们可以将其初始化为一个很大的数表示无穷大通常用INF表示。至此我们得到了“最优包含”问题的核心动态规划思路。它脱胎于编辑距离但根据具体操作和目标约束进行了关键的状态定义调整和转移简化。注意这里有一个非常重要的理解点。在编辑距离中dp[i][j]是“将A前i个变成B前j个”是一个“转换”的概念。在最优包含中dp[i][j]是“S前i个包含T前j个”是一个“包含”的概念。前者要求A的前i个整体发生变化后者只要求A的前i个中存在某个子序列。正是这个根本目标的差异导致了状态转移逻辑的不同。3. 动态规划状态设计与转移方程详解3.1 状态定义与初始化基于上一节的分析我们给出形式化的状态定义设字符串 S 和 T 的下标从 1 开始实际编码时通常从0开始但推导时从1开始更清晰。 定义二维数组dp[i][j]i的范围是 [0, n]表示考虑 S 的前 i 个字符。j的范围是 [0, m]表示要使得 S 的前 i 个字符包含 T 的前 j 个字符作为子序列。dp[i][j]的值表示达成上述目标所需的最少修改次数。初始化dp[0][0] 0空串包含空串无需修改。对于所有i从 0 到 ndp[i][0] 0任何字符串包括空串都包含空串作为子序列。对于所有j从 1 到 mdp[0][j] INF一个很大的数如0x3f3f3f3f空串不可能包含非空串 T 的前 j 个字符。这个初始化过程在编码时可以通过双重循环来完成先全部赋值为INF然后单独设置第一列j0为0。3.2 状态转移方程推导对于每个i(1 i n) 和j(1 j m)我们计算dp[i][j]。根据 S[i] 和 T[j] 是否相等以及我们是否使用 S[i] 来匹配 T[j]有两种决策决策一使用 S[i] 来匹配 T[j]。前提是我们在 S[1...i-1] 中已经匹配了 T[1...j-1]即状态来源于dp[i-1][j-1]。如果 S[i] T[j]那么直接匹配无需额外修改代价为dp[i-1][j-1] 0。如果 S[i] ! T[j]那么我们必须修改 S[i] 为 T[j]代价为dp[i-1][j-1] 1。我们可以将这两种情况统一为dp[i-1][j-1] (S[i] ! T[j] ? 1 : 0)。这里(S[i] ! T[j] ? 1 : 0)是一个指示函数相等为0不等为1。决策二不使用 S[i] 来匹配 T[j]。这意味着匹配 T[1...j] 的任务完全由 S[1...i-1] 来完成。因此状态来源于dp[i-1][j]。注意这个决策是总是可行的无论 S[i] 是什么。因为我们选择“跳过”当前这个 S 的字符。我们的目标是最小化修改次数因此dp[i][j]应该取上述两种决策结果的最小值。综合得到状态转移方程dp[i][j] min(dp[i-1][j], dp[i-1][j-1] (S[i] ! T[j] ? 1 : 0))这个方程就是“最优包含”问题的核心。我们来仔细品味一下dp[i-1][j]对应“跳过 S[i]”。这是“最优包含”问题区别于“编辑距离”的关键之一。在编辑距离中如果跳过 A[i]即删除对应的是dp[i-1][j] 1因为删除是一个需要代价的操作。而在我们这里“跳过”不是操作只是决策所以代价是0。这反映了我们只能修改不能删除的特性。dp[i-1][j-1] cost对应“使用 S[i] 匹配 T[j]”。这与编辑距离中的“替换”或“匹配”操作逻辑一致。3.3 一个具体的计算示例假设 S “abcdef” T “ace”。n6, m3.初始化dp[i][0]0,dp[0][j]INF(j0)。我们手动计算几个关键状态来理解过程为了直观S和T下标从1开始dp[1][1]: 考虑 S[1]‘a’匹配 T[1]‘a’。决策1使用dp[0][0] (a!a?1:0) 0 0 0决策2跳过dp[0][1] INF所以dp[1][1] min(INF, 0) 0。意味着用“a”包含“a”无需修改。dp[2][1]: 考虑 S[1..2]“ab”匹配 T[1]‘a’。决策1使用S[2]‘b’匹配dp[1][0] (b!a?1:0) 0 1 1决策2跳过S[2]dp[1][1] 0所以dp[2][1] min(1, 0) 0。最优方案是跳过‘b’用‘a’来匹配所以还是0次修改。dp[2][2]: 考虑 S[1..2]“ab”匹配 T[1..2]“ac”。决策1使用S[2]‘b’匹配T[2]‘c’dp[1][1] (b!c?1:0) 0 1 1决策2跳过S[2]dp[1][2] INF因为用“a”不可能包含“ac”所以dp[2][2] min(1, INF) 1。必须修改‘b’为‘c’代价1。dp[3][2]: 考虑 S[1..3]“abc”匹配 T[1..2]“ac”。决策1使用S[3]‘c’匹配T[2]‘c’dp[2][1] (c!c?1:0) 0 0 0决策2跳过S[3]dp[2][2] 1所以dp[3][2] min(0, 1) 0。最优方案是用 S[1]‘a’ 和 S[3]‘c’ 来匹配“ac”无需修改。最终dp[6][3]就是我们要求的答案表示整个 S 包含整个 T 所需的最少修改次数。通过填表计算我们可以得到结果。实操心得在手动推导或调试时画一个 (n1) x (m1) 的表格来模拟dp数组的填充过程非常有效。横向是 T 的字符索引 j纵向是 S 的字符索引 i。从左上角开始根据方程一行行或一列列计算。这个过程能帮你直观理解每个状态是如何依赖前驱状态的对于发现转移方程的错误或理解算法逻辑至关重要。4. 算法实现与代码解析理论分析透彻后我们来看如何用代码实现。这里我会给出两种常见的实现方式基于二维数组的标准DP以及优化了空间复杂度的滚动数组DP。我会用C和Python两种语言作为示例并详细解释关键代码段。4.1 标准二维DP实现C这是最直观的实现方式直接开辟一个(n1) x (m1)的二维数组。#include iostream #include string #include vector #include algorithm #include climits using namespace std; int main() { string S, T; cin S T; int n S.size(), m T.size(); // 定义dp数组并初始化为一个很大的数 const int INF 0x3f3f3f3f; vectorvectorint dp(n 1, vectorint(m 1, INF)); // 初始化对于所有idp[i][0] 0 for (int i 0; i n; i) { dp[i][0] 0; } // 状态转移 for (int i 1; i n; i) { for (int j 1; j m; j) { // 决策1跳过S的第i个字符在代码中下标是i-1 dp[i][j] dp[i-1][j]; // 决策2使用S的第i个字符匹配T的第j个字符 int cost (S[i-1] T[j-1]) ? 0 : 1; dp[i][j] min(dp[i][j], dp[i-1][j-1] cost); } } // 输出结果dp[n][m] 表示用S的全部包含T的全部 cout dp[n][m] endl; return 0; }代码关键点解析下标处理代码中S和T的下标从0开始但dp数组的下标i和j表示长度考虑前i/j个字符。因此当我们要访问字符串的第i个字符时对应的是S[i-1]和T[j-1]。这是初学者最容易混淆的地方务必小心。INF 的设置0x3f3f3f3f是一个常用的“无穷大”值因为它大约等于10^9在int范围内并且两个这样的数相加不会溢出int。在初始化时我们将所有dp[i][j]设为 INF然后单独将第一列设为0。转移顺序我们使用两层循环外层i从1到n内层j从1到m。这个顺序保证了当计算dp[i][j]时它所依赖的dp[i-1][j]和dp[i-1][j-1]都已经被计算出来了。这是一种标准的“行优先”遍历。状态转移代码清晰地对应了我们的方程。先取“跳过”决策的值 (dp[i-1][j])然后再与“使用”决策的值 (dp[i-1][j-1] cost) 比较取最小值。复杂度分析时间复杂度O(n * m)因为有两层嵌套循环。空间复杂度O(n * m)用于存储整个dp表。对于蓝桥杯等竞赛如果 n 和 m 在1000左右这个复杂度是完全可以接受的10^6 量级。但如果 n 和 m 达到 10^4 级别空间开销约 10^8 * 4 bytes ≈ 400MB可能会超过内存限制。这时就需要空间优化。4.2 空间优化滚动数组DPPython示例观察状态转移方程dp[i][j] min(dp[i-1][j], dp[i-1][j-1] cost)我们发现dp[i][...]只依赖于dp[i-1][...]。也就是说在计算第i行时我们只需要第i-1行的数据。因此我们不需要保存整个n x m的表格只需要保存两行当前行和上一行即可。这就是“滚动数组”优化。def optimal_inclusion(S: str, T: str) - int: n, m len(S), len(T) INF 10**9 # 初始化dp[0][j] 表示用空串包含T的前j个字符这是不可能的除了j0 # 我们使用两个一维数组prev 代表上一行 (i-1)curr 代表当前行 (i) prev [INF] * (m 1) prev[0] 0 # dp[0][0] 0 for i in range(1, n 1): # 初始化当前行。注意对于任何idp[i][0] 0 curr [0] [INF] * m # curr[0] 0, 其余为INF for j in range(1, m 1): # 决策1跳过 S[i-1] skip prev[j] # 决策2使用 S[i-1] 匹配 T[j-1] cost 0 if S[i-1] T[j-1] else 1 use prev[j-1] cost # 取最小值 curr[j] min(skip, use) # 当前行计算完毕成为下一轮的“上一行” prev curr # 循环结束后prev 保存的就是 dp[n][...] return prev[m] # 示例 if __name__ __main__: S input().strip() T input().strip() print(optimal_inclusion(S, T))代码关键点解析两个数组prev数组代表dp[i-1][...]curr数组代表dp[i][...]。初始化prevprev[j]对应dp[0][j]。除了prev[0]0其他都初始化为 INF。内层循环对于每个jprev[j]就是dp[i-1][j]prev[j-1]就是dp[i-1][j-1]。计算出的curr[j]就是新的dp[i][j]。行迭代每完成一行的计算就将curr赋值给prev用于下一轮计算。curr的初始化注意curr[0]必须始终为0因为dp[i][0] 0对任意 i 成立。我们在创建curr列表时直接设置curr[0]0。复杂度分析时间复杂度依然是 O(n * m)。空间复杂度优化为 O(m)因为我们只存储了两行实际上可以只用一个数组但需要小心处理覆盖顺序用两个数组更清晰。滚动数组优化是竞赛中处理线性DP的常用技巧能有效降低内存消耗务必掌握。注意事项使用滚动数组时要特别注意状态的依赖关系。在这个问题里dp[i][j]依赖于dp[i-1][j]和dp[i-1][j-1]。如果我们只用一维数组dp[j]并在原数组上更新当从左到右更新dp[j]时dp[j-1]已经被新一行的值覆盖了它本应是旧一行的值这会导致错误。因此要么像上面一样用两个数组要么用一维数组但从右向左更新j这样dp[j-1]在更新dp[j]时还是旧值。对于初学者强烈建议先用二维数组写对再转化为滚动数组并仔细验证。5. 边界条件、陷阱与实战技巧动态规划题目思路对了方程写了但最后可能因为边界条件或者一些细节没处理好而丢分。这部分我结合自己的踩坑经验总结几个在实现“最优包含”问题时需要特别注意的地方。5.1 边界条件的再审视dp[0][j] (j0)的初始化必须设置为一个“不可达”的大数INF。因为用空串去匹配非空子序列是不可能的。如果你初始化为0会导致后续状态计算出错因为 min 操作会误以为这是可达的。INF 的值要足够大大于任何可能的合法答案但又不能太大导致加法溢出。通常用0x3f3f3f3fC或10**9Python是安全的选择。dp[i][0]的初始化必须为0。这表示匹配空串总是成功的且代价为0。这个初始化要在开始状态转移之前完成。字符串下标这是最最常见的错误来源。我们的状态dp[i][j]中的i和j是长度不是下标。当需要比较字符时访问的是S[i-1]和T[j-1]。在写循环时务必保持清醒。一个建议是在代码中让i和j从1开始循环到 n 和 m但在访问字符串时使用i-1和j-1。这样逻辑最清晰。5.2 一个易错点关于“匹配”和“包含”的再理解我们定义的状态是“S的前i个字符包含T的前j个字符”。注意是“包含”而不是“以第i个字符结尾来匹配”。这意味着dp[i][j]的值可能来自于dp[i-1][j]即不使用 S[i]。所以在状态转移时dp[i][j]的初始值或者其中一个候选值就是dp[i-1][j]。有些同学可能会错误地认为如果 S[i] 不匹配 T[j]那么dp[i][j]就只能等于dp[i-1][j-1]1而忽略了“跳过 S[i]”这个选项。这会导致答案偏大。例如S“ab”, T“a”。最优方案是跳过 ‘b’用 ‘a’ 匹配修改次数为0。如果忽略了跳过选项可能会得到需要修改 ‘b’ 的错误答案。5.3 竞赛中的输入输出与性能考量输入格式蓝桥杯等竞赛的题目输入通常是两个字符串可能在同一行用空格隔开也可能分两行。用cin S T或input().split()可以轻松处理。务必先看清题目说明。输出格式通常就是一个整数。数据范围这是选择算法和优化方式的关键。如果题目给出 n, m 1000那么 O(nm) 的二维DP完全没问题。如果 n, m 10000二维数组约400MB可能超内存必须使用滚动数组优化到 O(m)。如果 n, m 更大比如10^5O(nm) 的复杂度就无法承受了可能需要更高级的算法如利用序列自动机进行优化但这通常超出了“最优包含”原题的考察范围国赛真题的数据范围一般会控制在二维DP可解之内。初始化 INF 的技巧在C中可以用memset(dp, 0x3f, sizeof(dp))来快速将整个数组初始化为0x3f3f3f3f。但要注意memset是按字节赋值的0x3f对于每个字节是相同的所以整个int就是0x3f3f3f3f。这是一个常用技巧。5.4 调试与验证技巧当你写完代码不确定是否正确时可以构造一些小数据进行测试。极端数据S 和 T 完全相同答案应为0。S 和 T 完全不同且长度相等答案应为 m需要修改 S 中 m 个位置以匹配 T 的每个字符。T 是空串答案应为0。S 是空串T 非空答案应为 INF或根据题目要求输出特定值。手动模拟数据像第3.3节那样用一个简单的例子如 S“abc”, T“ac”手动计算dp表然后与程序输出对比。这是最有效的调试方法之一。打印 DP 表在调试时可以临时将dp数组打印出来检查每个值是否符合预期。这对于理解状态转移和发现下标错误非常有帮助。6. 从“最优包含”到更广泛的字符串DP问题“最优包含”问题虽然有了定式但它的价值更在于其代表的解题范式。很多字符串相关的动态规划问题都可以从编辑距离和子序列匹配这两个基本模型演化而来。掌握“最优包含”的核心——状态定义如何体现“包含”而非“转换”以及转移方程如何反映“可选匹配”能帮你解决一大类问题。6.1 相关变种问题举例最长公共子序列LCS求两个字符串最长的公共子序列长度。其状态dp[i][j]定义为 S 前 i 个和 T 前 j 个的 LCS 长度。转移方程为若 S[i]T[j]dp[i][j] dp[i-1][j-1] 1若 S[i]!T[j]dp[i][j] max(dp[i-1][j], dp[i][j-1])这和“最优包含”的思维很像都是考虑当前字符是否用于匹配。LCS 求的是最大长度而“最优包含”求的是最小修改代价。通配符匹配/正则表达式匹配这类问题中模式串可能包含*(匹配零个或多个) 或?(匹配任意一个) 等特殊字符。状态dp[i][j]表示主串前 i 个和模式串前 j 个是否能匹配。转移时需要根据模式串当前字符是普通字符、?还是*来设计不同的逻辑。其复杂度在于*的处理它引入了“匹配零个”和“匹配多个”的决策和“最优包含”中“跳过”的决策有思想上的关联。不同的子序列给定字符串 S 和 T计算 S 的子序列中等于 T 的个数。状态dp[i][j]表示 S 的前 i 个字符中子序列等于 T 的前 j 个字符的个数。转移时考虑是否使用 S[i] 来匹配 T[j]如果不使用 S[i]方案数为dp[i-1][j]。如果 S[i] T[j]还可以使用 S[i]方案数加上dp[i-1][j-1]。 这几乎是“最优包含”的“计数版本”。6.2 如何识别这类DP问题在竞赛中遇到新的字符串问题如何判断它可能是一个动态规划问题并且可能与编辑距离或子序列相关呢我总结了几条线索问题涉及两个序列通常是字符串这是最明显的信号。目标是最优化最小操作数、最大长度、最多数量或可行性判断。操作或匹配规则是局部的当前步骤的决策只依赖于前面部分的结果和当前处理的字符。存在“匹配”或“包含”的概念不要求连续但要求顺序。当你识别出这些特征后就可以尝试定义dp[i][j]并思考在已知dp[0..i-1][0..j-1]的情况下如何通过决策 S[i] 和 T[j] 的关系推导出dp[i][j]。通常决策无非就是“用”还是“不用”当前字符。6.3 个人实战心得与编码建议最后分享几点我在竞赛中处理这类题目时的个人习惯先写状态定义注释在代码开头用注释清晰地写出dp[i][j]的含义。这能强迫你理清思路也便于后续调试。统一使用1-based索引进行思考在推导方程时假设字符串下标从1开始可以避免很多±1的混乱。在写代码时再转换为0-based索引。从简单到复杂如果直接想状态转移有困难先想暴力搜索怎么做虽然不可行然后思考暴力搜索中有哪些重复计算这些重复计算就是动态规划需要记忆的状态。测试驱动写完代码后不要只依赖样例。自己构造几个小的测试用例包括边界情况手动计算预期结果再与程序输出对比。空间优化放在最后除非题目数据范围明确要求否则先写出正确清晰的二维DP版本。确保正确后再考虑是否要优化为滚动数组。清晰的逻辑比一点空间优化更重要。“最优包含”作为一个经典的动态规划变种题其价值不仅在于解决这一个问题更在于它提供了一种分析字符串匹配类DP的范式。下次你在蓝桥杯国赛或者其他地方遇到类似的题目希望你能回想起这篇内容里的分析过程从容地定义状态、推导方程、避开陷阱稳稳地拿下分数。
从编辑距离到最优包含：动态规划在字符串匹配中的实战变种
1. 从“编辑距离”到“最优包含”一个经典算法的竞赛实战如果你刷过力扣或者准备过蓝桥杯国赛那么“编辑距离”这个词你一定不陌生。它几乎是动态规划入门必学的经典例题用来衡量两个字符串的相似度。但算法竞赛的魅力就在于它不会直接考你课本上的原题而是会把经典模型藏在一个全新的问题场景后面等着你去发现和拆解。“最优包含”就是这样一个典型的例子。我第一次在蓝桥杯国赛的模拟题里遇到它时第一反应也是去套编辑距离的模板结果发现有点对不上仔细琢磨后才恍然大悟——这其实是编辑距离思想的一个精妙变种考察的是你对状态定义和转移方程本质的理解而不仅仅是背诵模板。简单来说“最优包含”问题可以这样描述给定两个字符串 S 和 T我们可以对字符串 S 进行若干次操作每次操作可以修改 S 中的一个字符为任意字符目标是使得操作后的 S 包含子序列 T。这里“包含”指的是 T 是 S 的一个子序列不要求连续但顺序必须一致。我们需要求出最少的操作次数。这听起来是不是和“通过最少的编辑操作增、删、改将 S 变为 T”的编辑距离问题有异曲同工之妙没错核心的动态规划思想是相通的但状态定义和转移逻辑需要根据“子序列包含”这个新约束进行重塑。理解这个重塑的过程比你多刷十道模板题更有价值。这篇内容我就以一个过来人的身份带你彻底拆解“最优包含”问题。我不会只给你最终的状态转移方程那样毫无意义。我会从最朴素的暴力思路开始一步步推导为什么需要动态规划如何设计状态状态之间如何转移并重点对比它与标准编辑距离的异同。最后我会分享在竞赛实战中如何快速识别这类“变种题”以及编码时有哪些一写就错的坑。无论你是正在备战蓝桥杯、ACM还是单纯想深化对动态规划的理解相信这篇都能给你带来实实在在的收获。2. 问题本质分析与思路演进2.1 问题重述与核心约束解析首先我们明确一下“最优包含”问题的形式化定义输入两个字符串 S 和 T长度分别为 n 和 m (1 m n)。操作每次操作可以将 S 中的任意一个字符修改为任意其他字符通常是小写字母。注意只能修改不能插入或删除。这是与编辑距离的第一个关键区别。目标通过对 S 进行若干次可以为0修改操作使得 T 成为操作后字符串 S 的一个子序列。输出达成目标所需的最少修改次数。这里有几个关键约束需要吃透操作唯一性只有“修改”一种操作。在编辑距离中我们通常有插入、删除、替换三种操作。而这里S 的长度 n 是固定的我们无法改变其长度只能改变其内容。这直接影响了状态转移的可能性。目标宽松性目标是 T 成为 S 的子序列而非子串。这意味着 T 的字符在 S 中可以不连续出现只要相对顺序保持一致即可。例如T“abc”那么 S“axxbxxc” 是包含 T 作为子序列的S中的第1、4、7个字符依次构成了“abc”。这个“不连续”的特性是设计状态转移方程的核心。最小化修改我们关心的是最少的修改次数而不是是否能够达成。这天然指向了最优化问题动态规划是首选工具。理解这些约束后一个最朴素的想法是枚举 S 中所有长度为 m 的子序列虽然不要求连续但我们可以考虑匹配顺序然后计算将 S 中对应位置的字符修改为 T 中字符所需的次数取最小值。然而S 中长度为 m 的子序列数量是组合数 C(n, m)当 n 和 m 达到几百时这个数量是天文数字暴力枚举完全不可行。这就迫使我们寻找更聪明的办法——动态规划。2.2 从编辑距离到最优包含思路的迁移与调整既然暴力不行我们自然想到经典的编辑距离Levenshtein Distance模型。标准编辑距离的 DP 状态dp[i][j]通常定义为将字符串 A 的前 i 个字符转换为字符串 B 的前 j 个字符所需的最少操作次数。操作包括增、删、改。如果我们生搬硬套定义dp[i][j]为“将 S 的前 i 个字符通过修改操作变成包含 T 的前 j 个字符作为子序列所需的最少操作次数”会立刻遇到问题操作不匹配编辑距离有“增”、“删”而我们这里只有“改”。如果 S[i] 不等于 T[j]在编辑距离中我们可以选择删除 S[i]dp[i-1][j] 1或者插入 T[j]dp[i][j-1] 1。但在“最优包含”里S 的长度不能变我们不能删除 S[i]也不能插入字符。我们只能选择是否用 S[i] 去匹配 T[j]。目标不匹配编辑距离的目标是完全相等而我们的目标是“包含子序列”。这意味着对于 S 的前 i 个字符我们并不需要它们完全“变成” T 的前 j 个字符而是只需要从中找到一个子序列等于 T 的前 j 个字符即可。S 中未被用于匹配的字符可以保持原样只要不影响匹配。因此我们需要重新设计状态以贴合我们唯一的“修改”操作和“子序列包含”的目标。正确的思路是我们关注的是“匹配进度”。即我们正在用 S 的前 i 个字符去尝试匹配 T 的前 j 个字符看最少需要修改多少次才能让这个匹配成功。一个更精准的状态定义是dp[i][j]表示考虑 S 的前 i 个字符要使其包含 T 的前 j 个字符作为子序列所需的最少修改次数。注意这里“包含”意味着在 S[1...i] 这个前缀中存在一个子序列等于 T[1...j]。有了这个状态我们来思考转移。当我们处理到 S[i] 和 T[j] 时我们面临一个选择是否让 S[i] 参与匹配 T[j]情况一让 S[i] 参与匹配 T[j]。这要求 S[i] 最终必须等于 T[j]。如果原本 S[i] T[j]那么我们不需要修改直接使用它代价为0。如果 S[i] ! T[j]那么我们必须修改 S[i] 为 T[j]代价为1。在做出这个选择后我们的任务就变成了用 S 的前 i-1 个字符去匹配 T 的前 j-1 个字符。因此转移为dp[i-1][j-1] cost其中cost为 0 或 1。情况二不让 S[i] 参与匹配 T[j]。这意味着我们“跳过”了 S[i]不使用它来匹配当前 T 的第 j 个字符。那么匹配 T 的前 j 个字符的任务完全由 S 的前 i-1 个字符来承担。因此转移为dp[i-1][j]。我们需要的是最少修改次数所以dp[i][j]应该取上述两种情况的最小值。此外我们还需要考虑边界条件当 j 0 时表示要匹配 T 的前 0 个字符空串。空串永远是任何字符串的子序列且不需要任何修改。所以对于任意 idp[i][0] 0。当 i 0 且 j 0 时表示用空串 S 去匹配非空的 T这是不可能的。我们可以将其初始化为一个很大的数表示无穷大通常用INF表示。至此我们得到了“最优包含”问题的核心动态规划思路。它脱胎于编辑距离但根据具体操作和目标约束进行了关键的状态定义调整和转移简化。注意这里有一个非常重要的理解点。在编辑距离中dp[i][j]是“将A前i个变成B前j个”是一个“转换”的概念。在最优包含中dp[i][j]是“S前i个包含T前j个”是一个“包含”的概念。前者要求A的前i个整体发生变化后者只要求A的前i个中存在某个子序列。正是这个根本目标的差异导致了状态转移逻辑的不同。3. 动态规划状态设计与转移方程详解3.1 状态定义与初始化基于上一节的分析我们给出形式化的状态定义设字符串 S 和 T 的下标从 1 开始实际编码时通常从0开始但推导时从1开始更清晰。 定义二维数组dp[i][j]i的范围是 [0, n]表示考虑 S 的前 i 个字符。j的范围是 [0, m]表示要使得 S 的前 i 个字符包含 T 的前 j 个字符作为子序列。dp[i][j]的值表示达成上述目标所需的最少修改次数。初始化dp[0][0] 0空串包含空串无需修改。对于所有i从 0 到 ndp[i][0] 0任何字符串包括空串都包含空串作为子序列。对于所有j从 1 到 mdp[0][j] INF一个很大的数如0x3f3f3f3f空串不可能包含非空串 T 的前 j 个字符。这个初始化过程在编码时可以通过双重循环来完成先全部赋值为INF然后单独设置第一列j0为0。3.2 状态转移方程推导对于每个i(1 i n) 和j(1 j m)我们计算dp[i][j]。根据 S[i] 和 T[j] 是否相等以及我们是否使用 S[i] 来匹配 T[j]有两种决策决策一使用 S[i] 来匹配 T[j]。前提是我们在 S[1...i-1] 中已经匹配了 T[1...j-1]即状态来源于dp[i-1][j-1]。如果 S[i] T[j]那么直接匹配无需额外修改代价为dp[i-1][j-1] 0。如果 S[i] ! T[j]那么我们必须修改 S[i] 为 T[j]代价为dp[i-1][j-1] 1。我们可以将这两种情况统一为dp[i-1][j-1] (S[i] ! T[j] ? 1 : 0)。这里(S[i] ! T[j] ? 1 : 0)是一个指示函数相等为0不等为1。决策二不使用 S[i] 来匹配 T[j]。这意味着匹配 T[1...j] 的任务完全由 S[1...i-1] 来完成。因此状态来源于dp[i-1][j]。注意这个决策是总是可行的无论 S[i] 是什么。因为我们选择“跳过”当前这个 S 的字符。我们的目标是最小化修改次数因此dp[i][j]应该取上述两种决策结果的最小值。综合得到状态转移方程dp[i][j] min(dp[i-1][j], dp[i-1][j-1] (S[i] ! T[j] ? 1 : 0))这个方程就是“最优包含”问题的核心。我们来仔细品味一下dp[i-1][j]对应“跳过 S[i]”。这是“最优包含”问题区别于“编辑距离”的关键之一。在编辑距离中如果跳过 A[i]即删除对应的是dp[i-1][j] 1因为删除是一个需要代价的操作。而在我们这里“跳过”不是操作只是决策所以代价是0。这反映了我们只能修改不能删除的特性。dp[i-1][j-1] cost对应“使用 S[i] 匹配 T[j]”。这与编辑距离中的“替换”或“匹配”操作逻辑一致。3.3 一个具体的计算示例假设 S “abcdef” T “ace”。n6, m3.初始化dp[i][0]0,dp[0][j]INF(j0)。我们手动计算几个关键状态来理解过程为了直观S和T下标从1开始dp[1][1]: 考虑 S[1]‘a’匹配 T[1]‘a’。决策1使用dp[0][0] (a!a?1:0) 0 0 0决策2跳过dp[0][1] INF所以dp[1][1] min(INF, 0) 0。意味着用“a”包含“a”无需修改。dp[2][1]: 考虑 S[1..2]“ab”匹配 T[1]‘a’。决策1使用S[2]‘b’匹配dp[1][0] (b!a?1:0) 0 1 1决策2跳过S[2]dp[1][1] 0所以dp[2][1] min(1, 0) 0。最优方案是跳过‘b’用‘a’来匹配所以还是0次修改。dp[2][2]: 考虑 S[1..2]“ab”匹配 T[1..2]“ac”。决策1使用S[2]‘b’匹配T[2]‘c’dp[1][1] (b!c?1:0) 0 1 1决策2跳过S[2]dp[1][2] INF因为用“a”不可能包含“ac”所以dp[2][2] min(1, INF) 1。必须修改‘b’为‘c’代价1。dp[3][2]: 考虑 S[1..3]“abc”匹配 T[1..2]“ac”。决策1使用S[3]‘c’匹配T[2]‘c’dp[2][1] (c!c?1:0) 0 0 0决策2跳过S[3]dp[2][2] 1所以dp[3][2] min(0, 1) 0。最优方案是用 S[1]‘a’ 和 S[3]‘c’ 来匹配“ac”无需修改。最终dp[6][3]就是我们要求的答案表示整个 S 包含整个 T 所需的最少修改次数。通过填表计算我们可以得到结果。实操心得在手动推导或调试时画一个 (n1) x (m1) 的表格来模拟dp数组的填充过程非常有效。横向是 T 的字符索引 j纵向是 S 的字符索引 i。从左上角开始根据方程一行行或一列列计算。这个过程能帮你直观理解每个状态是如何依赖前驱状态的对于发现转移方程的错误或理解算法逻辑至关重要。4. 算法实现与代码解析理论分析透彻后我们来看如何用代码实现。这里我会给出两种常见的实现方式基于二维数组的标准DP以及优化了空间复杂度的滚动数组DP。我会用C和Python两种语言作为示例并详细解释关键代码段。4.1 标准二维DP实现C这是最直观的实现方式直接开辟一个(n1) x (m1)的二维数组。#include iostream #include string #include vector #include algorithm #include climits using namespace std; int main() { string S, T; cin S T; int n S.size(), m T.size(); // 定义dp数组并初始化为一个很大的数 const int INF 0x3f3f3f3f; vectorvectorint dp(n 1, vectorint(m 1, INF)); // 初始化对于所有idp[i][0] 0 for (int i 0; i n; i) { dp[i][0] 0; } // 状态转移 for (int i 1; i n; i) { for (int j 1; j m; j) { // 决策1跳过S的第i个字符在代码中下标是i-1 dp[i][j] dp[i-1][j]; // 决策2使用S的第i个字符匹配T的第j个字符 int cost (S[i-1] T[j-1]) ? 0 : 1; dp[i][j] min(dp[i][j], dp[i-1][j-1] cost); } } // 输出结果dp[n][m] 表示用S的全部包含T的全部 cout dp[n][m] endl; return 0; }代码关键点解析下标处理代码中S和T的下标从0开始但dp数组的下标i和j表示长度考虑前i/j个字符。因此当我们要访问字符串的第i个字符时对应的是S[i-1]和T[j-1]。这是初学者最容易混淆的地方务必小心。INF 的设置0x3f3f3f3f是一个常用的“无穷大”值因为它大约等于10^9在int范围内并且两个这样的数相加不会溢出int。在初始化时我们将所有dp[i][j]设为 INF然后单独将第一列设为0。转移顺序我们使用两层循环外层i从1到n内层j从1到m。这个顺序保证了当计算dp[i][j]时它所依赖的dp[i-1][j]和dp[i-1][j-1]都已经被计算出来了。这是一种标准的“行优先”遍历。状态转移代码清晰地对应了我们的方程。先取“跳过”决策的值 (dp[i-1][j])然后再与“使用”决策的值 (dp[i-1][j-1] cost) 比较取最小值。复杂度分析时间复杂度O(n * m)因为有两层嵌套循环。空间复杂度O(n * m)用于存储整个dp表。对于蓝桥杯等竞赛如果 n 和 m 在1000左右这个复杂度是完全可以接受的10^6 量级。但如果 n 和 m 达到 10^4 级别空间开销约 10^8 * 4 bytes ≈ 400MB可能会超过内存限制。这时就需要空间优化。4.2 空间优化滚动数组DPPython示例观察状态转移方程dp[i][j] min(dp[i-1][j], dp[i-1][j-1] cost)我们发现dp[i][...]只依赖于dp[i-1][...]。也就是说在计算第i行时我们只需要第i-1行的数据。因此我们不需要保存整个n x m的表格只需要保存两行当前行和上一行即可。这就是“滚动数组”优化。def optimal_inclusion(S: str, T: str) - int: n, m len(S), len(T) INF 10**9 # 初始化dp[0][j] 表示用空串包含T的前j个字符这是不可能的除了j0 # 我们使用两个一维数组prev 代表上一行 (i-1)curr 代表当前行 (i) prev [INF] * (m 1) prev[0] 0 # dp[0][0] 0 for i in range(1, n 1): # 初始化当前行。注意对于任何idp[i][0] 0 curr [0] [INF] * m # curr[0] 0, 其余为INF for j in range(1, m 1): # 决策1跳过 S[i-1] skip prev[j] # 决策2使用 S[i-1] 匹配 T[j-1] cost 0 if S[i-1] T[j-1] else 1 use prev[j-1] cost # 取最小值 curr[j] min(skip, use) # 当前行计算完毕成为下一轮的“上一行” prev curr # 循环结束后prev 保存的就是 dp[n][...] return prev[m] # 示例 if __name__ __main__: S input().strip() T input().strip() print(optimal_inclusion(S, T))代码关键点解析两个数组prev数组代表dp[i-1][...]curr数组代表dp[i][...]。初始化prevprev[j]对应dp[0][j]。除了prev[0]0其他都初始化为 INF。内层循环对于每个jprev[j]就是dp[i-1][j]prev[j-1]就是dp[i-1][j-1]。计算出的curr[j]就是新的dp[i][j]。行迭代每完成一行的计算就将curr赋值给prev用于下一轮计算。curr的初始化注意curr[0]必须始终为0因为dp[i][0] 0对任意 i 成立。我们在创建curr列表时直接设置curr[0]0。复杂度分析时间复杂度依然是 O(n * m)。空间复杂度优化为 O(m)因为我们只存储了两行实际上可以只用一个数组但需要小心处理覆盖顺序用两个数组更清晰。滚动数组优化是竞赛中处理线性DP的常用技巧能有效降低内存消耗务必掌握。注意事项使用滚动数组时要特别注意状态的依赖关系。在这个问题里dp[i][j]依赖于dp[i-1][j]和dp[i-1][j-1]。如果我们只用一维数组dp[j]并在原数组上更新当从左到右更新dp[j]时dp[j-1]已经被新一行的值覆盖了它本应是旧一行的值这会导致错误。因此要么像上面一样用两个数组要么用一维数组但从右向左更新j这样dp[j-1]在更新dp[j]时还是旧值。对于初学者强烈建议先用二维数组写对再转化为滚动数组并仔细验证。5. 边界条件、陷阱与实战技巧动态规划题目思路对了方程写了但最后可能因为边界条件或者一些细节没处理好而丢分。这部分我结合自己的踩坑经验总结几个在实现“最优包含”问题时需要特别注意的地方。5.1 边界条件的再审视dp[0][j] (j0)的初始化必须设置为一个“不可达”的大数INF。因为用空串去匹配非空子序列是不可能的。如果你初始化为0会导致后续状态计算出错因为 min 操作会误以为这是可达的。INF 的值要足够大大于任何可能的合法答案但又不能太大导致加法溢出。通常用0x3f3f3f3fC或10**9Python是安全的选择。dp[i][0]的初始化必须为0。这表示匹配空串总是成功的且代价为0。这个初始化要在开始状态转移之前完成。字符串下标这是最最常见的错误来源。我们的状态dp[i][j]中的i和j是长度不是下标。当需要比较字符时访问的是S[i-1]和T[j-1]。在写循环时务必保持清醒。一个建议是在代码中让i和j从1开始循环到 n 和 m但在访问字符串时使用i-1和j-1。这样逻辑最清晰。5.2 一个易错点关于“匹配”和“包含”的再理解我们定义的状态是“S的前i个字符包含T的前j个字符”。注意是“包含”而不是“以第i个字符结尾来匹配”。这意味着dp[i][j]的值可能来自于dp[i-1][j]即不使用 S[i]。所以在状态转移时dp[i][j]的初始值或者其中一个候选值就是dp[i-1][j]。有些同学可能会错误地认为如果 S[i] 不匹配 T[j]那么dp[i][j]就只能等于dp[i-1][j-1]1而忽略了“跳过 S[i]”这个选项。这会导致答案偏大。例如S“ab”, T“a”。最优方案是跳过 ‘b’用 ‘a’ 匹配修改次数为0。如果忽略了跳过选项可能会得到需要修改 ‘b’ 的错误答案。5.3 竞赛中的输入输出与性能考量输入格式蓝桥杯等竞赛的题目输入通常是两个字符串可能在同一行用空格隔开也可能分两行。用cin S T或input().split()可以轻松处理。务必先看清题目说明。输出格式通常就是一个整数。数据范围这是选择算法和优化方式的关键。如果题目给出 n, m 1000那么 O(nm) 的二维DP完全没问题。如果 n, m 10000二维数组约400MB可能超内存必须使用滚动数组优化到 O(m)。如果 n, m 更大比如10^5O(nm) 的复杂度就无法承受了可能需要更高级的算法如利用序列自动机进行优化但这通常超出了“最优包含”原题的考察范围国赛真题的数据范围一般会控制在二维DP可解之内。初始化 INF 的技巧在C中可以用memset(dp, 0x3f, sizeof(dp))来快速将整个数组初始化为0x3f3f3f3f。但要注意memset是按字节赋值的0x3f对于每个字节是相同的所以整个int就是0x3f3f3f3f。这是一个常用技巧。5.4 调试与验证技巧当你写完代码不确定是否正确时可以构造一些小数据进行测试。极端数据S 和 T 完全相同答案应为0。S 和 T 完全不同且长度相等答案应为 m需要修改 S 中 m 个位置以匹配 T 的每个字符。T 是空串答案应为0。S 是空串T 非空答案应为 INF或根据题目要求输出特定值。手动模拟数据像第3.3节那样用一个简单的例子如 S“abc”, T“ac”手动计算dp表然后与程序输出对比。这是最有效的调试方法之一。打印 DP 表在调试时可以临时将dp数组打印出来检查每个值是否符合预期。这对于理解状态转移和发现下标错误非常有帮助。6. 从“最优包含”到更广泛的字符串DP问题“最优包含”问题虽然有了定式但它的价值更在于其代表的解题范式。很多字符串相关的动态规划问题都可以从编辑距离和子序列匹配这两个基本模型演化而来。掌握“最优包含”的核心——状态定义如何体现“包含”而非“转换”以及转移方程如何反映“可选匹配”能帮你解决一大类问题。6.1 相关变种问题举例最长公共子序列LCS求两个字符串最长的公共子序列长度。其状态dp[i][j]定义为 S 前 i 个和 T 前 j 个的 LCS 长度。转移方程为若 S[i]T[j]dp[i][j] dp[i-1][j-1] 1若 S[i]!T[j]dp[i][j] max(dp[i-1][j], dp[i][j-1])这和“最优包含”的思维很像都是考虑当前字符是否用于匹配。LCS 求的是最大长度而“最优包含”求的是最小修改代价。通配符匹配/正则表达式匹配这类问题中模式串可能包含*(匹配零个或多个) 或?(匹配任意一个) 等特殊字符。状态dp[i][j]表示主串前 i 个和模式串前 j 个是否能匹配。转移时需要根据模式串当前字符是普通字符、?还是*来设计不同的逻辑。其复杂度在于*的处理它引入了“匹配零个”和“匹配多个”的决策和“最优包含”中“跳过”的决策有思想上的关联。不同的子序列给定字符串 S 和 T计算 S 的子序列中等于 T 的个数。状态dp[i][j]表示 S 的前 i 个字符中子序列等于 T 的前 j 个字符的个数。转移时考虑是否使用 S[i] 来匹配 T[j]如果不使用 S[i]方案数为dp[i-1][j]。如果 S[i] T[j]还可以使用 S[i]方案数加上dp[i-1][j-1]。 这几乎是“最优包含”的“计数版本”。6.2 如何识别这类DP问题在竞赛中遇到新的字符串问题如何判断它可能是一个动态规划问题并且可能与编辑距离或子序列相关呢我总结了几条线索问题涉及两个序列通常是字符串这是最明显的信号。目标是最优化最小操作数、最大长度、最多数量或可行性判断。操作或匹配规则是局部的当前步骤的决策只依赖于前面部分的结果和当前处理的字符。存在“匹配”或“包含”的概念不要求连续但要求顺序。当你识别出这些特征后就可以尝试定义dp[i][j]并思考在已知dp[0..i-1][0..j-1]的情况下如何通过决策 S[i] 和 T[j] 的关系推导出dp[i][j]。通常决策无非就是“用”还是“不用”当前字符。6.3 个人实战心得与编码建议最后分享几点我在竞赛中处理这类题目时的个人习惯先写状态定义注释在代码开头用注释清晰地写出dp[i][j]的含义。这能强迫你理清思路也便于后续调试。统一使用1-based索引进行思考在推导方程时假设字符串下标从1开始可以避免很多±1的混乱。在写代码时再转换为0-based索引。从简单到复杂如果直接想状态转移有困难先想暴力搜索怎么做虽然不可行然后思考暴力搜索中有哪些重复计算这些重复计算就是动态规划需要记忆的状态。测试驱动写完代码后不要只依赖样例。自己构造几个小的测试用例包括边界情况手动计算预期结果再与程序输出对比。空间优化放在最后除非题目数据范围明确要求否则先写出正确清晰的二维DP版本。确保正确后再考虑是否要优化为滚动数组。清晰的逻辑比一点空间优化更重要。“最优包含”作为一个经典的动态规划变种题其价值不仅在于解决这一个问题更在于它提供了一种分析字符串匹配类DP的范式。下次你在蓝桥杯国赛或者其他地方遇到类似的题目希望你能回想起这篇内容里的分析过程从容地定义状态、推导方程、避开陷阱稳稳地拿下分数。
![[光学原理与应用-521]：对光的错误理解与纠偏](http://pic.xiahunao.cn/yaotu/[光学原理与应用-521]：对光的错误理解与纠偏)
