最长公共子序列的变种：最小ASCII删除和

题目描述
给定两个字符串 s1 和 s2，要求通过删除一些字符使得两个字符串相等。每删除一个字符，需要消耗该字符的ASCII码值。要求计算使两个字符串相等所需的最小删除ASCII码总和。

例如：

s1 = "sea", s2 = "eat"
删除 's' (ASCII 115) 和 't' (ASCII 116)，总消耗为 115 + 116 = 231
最终得到公共字符串 "ea"。

解题思路

1. 问题转化
   最小删除ASCII和等价于：保留两个字符串的公共子序列，且该子序列的ASCII码之和最大。
   因此，最小删除和 = 两个字符串的总ASCII和 - 2 × 最大公共子序列的ASCII和。

2. 动态规划定义
   设 dp[i][j] 表示 s1 的前 i 个字符与 s2 的前 j 个字符的最大公共子序列的ASCII和。

3. 状态转移

   • 若 s1[i-1] == s2[j-1]：
     当前字符可加入公共子序列，dp[i][j] = dp[i-1][j-1] + s1[i-1]的ASCII值。
   • 若不等：
     选择保留 s1 的当前字符或 s2 的当前字符中更优的情况：
     dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

4. 初始化

   • dp[0][j] = 0（空字符串与任何字符串的公共子序列ASCII和为0）
   • dp[i][0] = 0

5. 最终结果
   总ASCII和：sum1 = sum(ord(c) for c in s1)，sum2 = sum(ord(c) for c in s2)
   最小删除和 = sum1 + sum2 - 2 * dp[len(s1)][len(s2)]

详细步骤（以 s1="sea", s2="eat" 为例）

1. 计算总ASCII和：

   • sum1 = 115 + 101 + 97 = 313
   • sum2 = 101 + 97 + 116 = 314

2. 构建DP表（尺寸 4×4，因字符串长度均为3）：

      ""  e   a   t
   "" 0   0   0   0
   s  0   0   0   0
   e  0   101 101 101
   a  0   101 198 198
   

   • 第2行第2列：s1[0]='s' vs s2[0]='e'，不等，取 max(0,0)=0
   • 第3行第2列：s1[1]='e' vs s2[0]='e'，相等，dp[3][2] = 0 + 101 = 101
   • 第3行第3列：s1[1]='e' vs s2[1]='a'，不等，取 max(101,0)=101
   • 第4行第3列：s1[2]='a' vs s2[1]='a'，相等，dp[4][3] = 101 + 97 = 198

3. 最大公共子序列ASCII和 = dp[3][3] = 198（对应子序列"ea"）

4. 最小删除和 = 313 + 314 - 2 × 198 = 231

关键点

• 本题是最长公共子序列（LCS）的变种，将“长度”替换为“ASCII和”。
• 状态转移时，相等则累加字符值，不等则继承左侧或上侧的最大值。
• 最终通过总ASCII和减去两倍公共子序列的ASCII和得到删除代价。