线性动态规划：两个字符串的最小ASCII删除和

我们来看这样一个问题：
给定两个字符串 s1 和 s2，你可以删除任意个字符（包括 0 个），每次删除一个字符时，需要消耗该字符的 ASCII 码值作为代价。目标是使两个字符串相等（变成相同的字符串），求最小的删除总 ASCII 和。

1. 问题分析

例如：

s1 = "sea", s2 = "eat"

s1 删除 's' (ASCII 115) 后得到 "ea"，s2 删除 't' (ASCII 116) 后也得到 "ea"。
总代价 = 115 + 116 = 231。
这就是题目要求的最小 ASCII 删除和。

1.1 转换成公共子序列问题

让两个字符串相等，其实就是找到它们的一个公共子序列，然后删除不在这个公共子序列里的字符。
删除的总 ASCII 代价 = s1 所有字符的 ASCII 和 + s2 所有字符的 ASCII 和 − 2 × 公共子序列的 ASCII 和。

因为公共子序列的字符保留，两个字符串中非公共部分都要删除。

设：

• sum1 = s1 所有字符的 ASCII 总和
• sum2 = s2 所有字符的 ASCII 总和
• LCS_ascii_sum = 最长公共子序列中所有字符的 ASCII 和（不一定是最长，是总 ASCII 和最大的公共子序列）

则答案 = sum1 + sum2 − 2 × LCS_ascii_sum。

所以问题转化为：求两个字符串的“最大 ASCII 和的公共子序列”。

2. 动态规划定义

定义 dp[i][j] 表示 s1[0..i−1] 和 s2[0..j−1] 的最大 ASCII 和的公共子序列的 ASCII 和。

• 字符串索引从 1 到 n 方便表示。
• 初始：dp[0][j] = 0（s1 为空，公共子序列 ASCII 和为 0），dp[i][0] = 0 同理。

状态转移：

1. 如果 s1[i−1] == s2[j−1]，那么这个字符可以加入公共子序列：

   dp[i][j] = dp[i−1][j−1] + ascii(s1[i−1])
   

2. 如果 s1[i−1] != s2[j−1]，那么公共子序列可能来自：
   • s1[0..i−2] 与 s2[0..j−1] 的最大 ASCII 和公共子序列
   • s1[0..i−1] 与 s2[0..j−2] 的最大 ASCII 和公共子序列
     取较大者：

   dp[i][j] = max(dp[i−1][j], dp[i][j−1])
   

3. 举例演算

s1 = "sea", s2 = "eat"

• ASCII: 's'=115, 'e'=101, 'a'=97, 't'=116
  sum1 = 115+101+97 = 313
sum2 = 101+97+116 = 314

DP 表格（dp[i][j] = 最大 ASCII 和的公共子序列的 ASCII 和）：

初始：

   '' e  a  t
'' 0  0  0  0
s  0
e  0
a  0

步骤（省略空字符串行首）：

1. i=1('s'), j=1('e'): 不同 → max(0,0)=0
2. i=1('s'), j=2('a'): 不同 → max(0,0)=0
3. i=1('s'), j=3('t'): 不同 → max(0,0)=0
4. i=2('e'), j=1('e'): 相同 → 0+101=101
5. i=2('e'), j=2('a'): 不同 → max(dp[1][2]=0, dp[2][1]=101) = 101
6. i=2('e'), j=3('t'): 不同 → max(dp[1][3]=0, dp[2][2]=101) = 101
7. i=3('a'), j=1('e'): 不同 → max(dp[2][1]=101, dp[3][0]=0)=101
8. i=3('a'), j=2('a'): 相同 → dp[2][1]=101 + 97 = 198
9. i=3('a'), j=3('t'): 不同 → max(dp[2][3]=101, dp[3][2]=198)=198

最终 dp[3][3] = 198。

验证：最大 ASCII 和的公共子序列是 "ea"（ASCII 和 101+97=198）。

4. 计算结果

sum1 = 313, sum2 = 314, LCS_ascii_sum = 198
答案 = 313 + 314 − 2 × 198 = 627 − 396 = 231，与例子一致。

5. 核心代码思路

def minimumDeleteSum(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + ord(s1[i-1])
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    total = sum(ord(c) for c in s1) + sum(ord(c) for c in s2)
    return total - 2*dp[m][n]

6. 复杂度

• 时间：O(m×n)
• 空间：O(m×n)，可以优化到 O(min(m,n))

这个问题本质是最长公共子序列的带权版本（权值是 ASCII 码值），通过 DP 求出最大权值公共子序列的权值和，再用总和减去两倍得到最小删除代价。