最长公共子序列的变种：最小ASCII删除和 题目描述 给定两个字符串 s1 和 s2 ，我们需要通过删除一些字符（可以是0个）使得两个字符串相等。每次删除操作会删除一个字符，并且这个字符的ASCII值会被计入“删除成本”。我们的目标是找到使两个字符串相等所需的最小ASCII删除和。 换句话说，我们需要找到两个字符串的一个公共子序列，使得这个公共子序列之外的字符的ASCII值之和最小。这个和就是最小的ASCII删除和。 示例 输入: s1 = "sea", s2 = "eat" 输出: 231 解释: 删除 "s" (ASCII 115) 和 "t" (ASCII 116) 剩余字符串 "ea" 是公共子序列 总成本 = 115 + 116 = 231 解题思路 这个问题是经典的最长公共子序列（LCS）问题的变种。在LCS问题中，我们寻找最长的公共子序列。而在这里，我们关心的是那些“不属于”公共子序列的字符的ASCII值之和。 核心转换 ：最小删除成本，等价于两个字符串的总ASCII和，减去公共子序列的最大ASCII和。 总成本 = sum(ASCII(s1)) + sum(ASCII(s2)) 如果我们能找到一个公共子序列 LCS ，其ASCII和为 sum(ASCII(LCS)) ，那么我们需要删除的字符的ASCII和就是 总成本 - 2 * sum(ASCII(LCS)) 。为什么是2倍？因为 LCS 同时存在于 s1 和 s2 中，我们保留它，就意味着我们不需要删除 s1 和 s2 中构成 LCS 的那些字符。我们删除的是 s1 中不属于 LCS 的字符和 s2 中不属于 LCS 的字符。 因此， 最小化删除和 等价于 最大化公共子序列的ASCII和 。 动态规划定义 ：我们定义一个二维DP数组。 设 dp[i][j] 表示字符串 s1 的前 i 个字符（即 s1[0...i-1] ）和字符串 s2 的前 j 个字符（即 s2[0...j-1] ）所形成的公共子序列的 最大ASCII和 。 我们的最终目标是 dp[m][n] ，其中 m 和 n 分别是 s1 和 s2 的长度。 状态转移方程 ：我们如何推导出 dp[i][j] ？ 基础情况 ： 如果 i == 0 或 j == 0 ，意味着其中一个字符串是空的。空字符串和任何字符串的公共子序列的ASCII和自然是0。所以 dp[0][j] = 0 对于所有 j ， dp[i][0] = 0 对于所有 i 。 一般情况 ( i > 0 且 j > 0 )： 情况1：如果 s1[i-1] == s2[j-1] (当前考虑的最后一个字符相等) 这个相等的字符必然属于公共子序列，并且能为我们贡献它的ASCII值。 那么， dp[i][j] 就等于在剩下的字符串（ s1 的前 i-1 个字符和 s2 的前 j-1 个字符）中找到的公共子序列的最大ASCII和，再加上这个相等字符的ASCII值。 转移方程： dp[i][j] = dp[i-1][j-1] + int(s1[i-1]) 情况2：如果 s1[i-1] != s2[j-1] (当前考虑的最后一个字符不相等) 那么，这两个字符不可能同时出现在当前的公共子序列中。我们有两种选择： 选择A ：放弃 s1 的最后一个字符（即 s1[i-1] ）。那么问题就转化为求 s1 的前 i-1 个字符和 s2 的前 j 个字符的公共子序列最大ASCII和，即 dp[i-1][j] 。 选择B ：放弃 s2 的最后一个字符（即 s2[j-1] ）。那么问题就转化为求 s1 的前 i 个字符和 s2 的前 j-1 个字符的公共子序列最大ASCII和，即 dp[i][j-1] 。 我们的目标是最大化ASCII和，所以我们应该在这两种选择中取最大值。 转移方程： dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 计算最终结果 ： 按照上述方程填充整个 (m+1) x (n+1) 的DP表。通常我们使用双重循环， i 从0到 m ， j 从0到 n 。 计算两个字符串的总ASCII和： total_ascii = sum(ord(c) for c in s1) + sum(ord(c) for c in s2) 最小的ASCII删除和 = total_ascii - 2 * dp[m][n] 循序渐进的计算过程（以示例 s1="sea", s2="eat" 为例） 初始化 ： m = 3 , n = 3 创建 dp 表，大小为 4x4 （索引从0到3）。第一行和第一列初始化为0。 s1 的ASCII和： 's'=115, 'e'=101, 'a'=97 -> 总和 = 115+101+97 = 313 s2 的ASCII和： 'e'=101, 'a'=97, 't'=116 -> 总和 = 101+97+116 = 314 total_ascii = 313 + 314 = 627 填充DP表 ： i=1, j=1 : 比较 s1[0]='s' 和 s2[0]='e' 不相等 -> dp[1][1] = max(dp[0][1], dp[1][0]) = max(0, 0) = 0 i=1, j=2 : 比较 s1[0]='s' 和 s2[1]='a' 不相等 -> dp[1][2] = max(dp[0][2], dp[1][1]) = max(0, 0) = 0 i=1, j=3 : 比较 s1[0]='s' 和 s2[2]='t' 不相等 -> dp[1][3] = max(dp[0][3], dp[1][2]) = max(0, 0) = 0 i=2, j=1 : 比较 s1[1]='e' 和 s2[0]='e' 相等 -> dp[2][1] = dp[1][0] + int('e') = 0 + 101 = 101 i=2, j=2 : 比较 s1[1]='e' 和 s2[1]='a' 不相等 -> dp[2][2] = max(dp[1][2], dp[2][1]) = max(0, 101) = 101 i=2, j=3 : 比较 s1[1]='e' 和 s2[2]='t' 不相等 -> dp[2][3] = max(dp[1][3], dp[2][2]) = max(0, 101) = 101 i=3, j=1 : 比较 s1[2]='a' 和 s2[0]='e' 不相等 -> dp[3][1] = max(dp[2][1], dp[3][0]) = max(101, 0) = 101 i=3, j=2 : 比较 s1[2]='a' 和 s2[1]='a' 相等 -> dp[3][2] = dp[2][1] + int('a') = 101 + 97 = 198 i=3, j=3 : 比较 s1[2]='a' 和 s2[2]='t' 不相等 -> dp[3][3] = max(dp[2][3], dp[3][2]) = max(101, 198) = 198 最终的DP表如下： | | "" | "e" | "ea" | "eat" | | :---- | :-: | :-: | :--: | :---: | | "" | 0 | 0 | 0 | 0 | | "s" | 0 | 0 | 0 | 0 | | "se" | 0 | 101 | 101 | 101 | | "sea" | 0 | 101 | 198 | 198 | 得出答案 ： 最大公共子序列ASCII和 dp[3][3] = 198 。这个公共子序列是 "ea"。 最小ASCII删除和 = total_ascii - 2 * dp[m][n] = 627 - 2 * 198 = 627 - 396 = 231 。 这个结果与示例中的解释完全一致。通过这个动态规划过程，我们成功地找到了使两个字符串相等所需的最小删除成本。