""  e   a   t
""  0   0   0   0
s   0   0   0   0
e   0   0   0   0
a   0   0   0   0

最长公共子序列的变种：最小ASCII删除和 题目描述 给定两个字符串s1和s2，你需要通过删除一些字符（可以是0个）使得两个字符串相等。每次删除操作会删除一个字符，并且该字符的ASCII值会被计入删除成本。请计算使两个字符串相等所需的最小ASCII删除和。 示例 输入：s1 = "sea", s2 = "eat" 输出：231 解释：删除's' (115) 和 't' (116)，总成本 = 115 + 116 = 231 解题思路 这个问题是最长公共子序列（LCS）的一个变种。在标准LCS中，我们寻找最长的公共子序列。而在这里，我们实际上是在寻找一个公共子序列，使得两个原字符串中"不属于"这个公共子序列的字符的ASCII值之和最小。换句话说，我们希望这个公共子序列的ASCII值之和尽可能大。 关键转换 计算两个字符串所有字符的ASCII值总和： total_ascii = sum(ascii(s1)) + sum(ascii(s2)) 找到两个字符串的ASCII值之和最大的公共子序列 最小删除和 = 总ASCII和 - 2 × 最大公共子序列的ASCII和 动态规划解法 我们定义dp[ i][ j ]表示s1的前i个字符和s2的前j个字符的最大公共子序列的ASCII值之和。 状态转移方程 如果s1[ i-1] == s2[ j-1 ]：这两个字符匹配，可以加入公共子序列 dp[i][j] = dp[i-1][j-1] + ascii(s1[i-1]) 如果s1[ i-1] != s2[ j-1 ]：字符不匹配，选择能使公共子序列ASCII和更大的方向 dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 边界条件 dp[ 0][ j ] = 0（s1为空字符串） dp[ i][ 0 ] = 0（s2为空字符串） 详细步骤 以s1 = "sea", s2 = "eat"为例： 初始化dp表格（大小：4×4）： 填充表格： 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 ] + ascii('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 ] + ascii('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 最终结果： 总ASCII和 = 115+101+97 + 101+97+116 = 627 最大公共子序列ASCII和 = dp[ 3][ 3 ] = 198 最小删除和 = 627 - 2×198 = 231 算法复杂度 时间复杂度：O(m×n)，其中m和n分别是两个字符串的长度 空间复杂度：O(m×n)，可以优化到O(min(m,n)) 这个解法通过动态规划找到了最优的公共子序列，从而计算出最小的删除成本。