LeetCode 712. 两个字符串的最小ASCII删除和
目录
题目描述
题意分析
给两个小写字母字符串
s1、s2，唯一允许的操作是从任意一个串里删掉一个字符，代价是该字符的 ASCII 值。目标是把两个串变成完全相同的字符串，并让删掉的所有字符的 ASCII 值之和最小。注意「变得相同」并不要求变成空串。删剩下的公共部分可以是任意长度，只要两边一模一样即可；因此本质上是在两个串里各保留一个相同的子序列，其余全删。
关键要看清楚这不是「删的字符个数最少」。代价按 ASCII 值加权，
'a'是 97、'z'是 122，所以删掉一个z比删掉一个a贵。这意味着不能简单套用「保留最长公共子序列」的结论——最长的公共子序列未必是 ASCII 总和最大的那个，比如保留一个z可能比保留两个a更划算。长度约束是
1 <= s1.length, s2.length <= 1000，$O(mn)$ 规模是一百万，完全能接受；这个量级正是在暗示「两个下标各自作为一维」的解法。而 $O(2^n)$ 级别的枚举显然不行。边界方面：题目保证两串非空，但递归/递推过程中一定会出现某一侧走空的情形，此时唯一的办法就是把另一侧剩下的字符全部删掉，这构成了状态的基准值。
解法：动态规划状态转移
核心思路
暴力做法是枚举
s1的所有子序列，检查它是否也是s2的子序列，再算删除代价取最小。s1长度 1000 时子序列有 $2^{1000}$ 个，彻底不可行。瓶颈在于把「保留哪些字符」当成了一个整体决策。而实际上，只要从两个串的同一端逐字符往前推，每一步的决策空间只有很少几种，且做完决策后剩下的问题和原问题形状完全相同、规模严格变小——这正是可以做动态规划的信号。
状态定义：
dp[i][j]表示把后缀s1[i:]和后缀s2[j:]变成相同字符串所需的最小删除 ASCII 和。答案就是dp[0][0]。之所以用后缀而不是前缀，只是与代码里从后往前的循环方向保持一致，用前缀写也完全等价。基准状态：
dp[m][j]表示s1已经空了，那么s2[j:]里的每个字符都没有配对对象，只能全删，值等于s2[j:]的 ASCII 总和；dp[i][n]同理。特别地dp[m][n] = 0，两边都空，不用删任何东西。转移只看两个后缀的首字符
s1[i]与s2[j]。如果它们相等，那么把这一对字符同时保留一定不劣——保留它不花任何代价，而且不会让剩余子问题变差，所以dp[i][j] = dp[i+1][j+1]。如果不相等，那么这两个字符至少要删掉一个（因为它们各自是所在后缀的第一个字符，只要都保留，最终串的首字符就会矛盾）。于是分两种选择：删s1[i]，代价s1[i] + dp[i+1][j]；删s2[j]，代价s2[j] + dp[i][j+1]。取两者较小值。「两个都删」这种情况不用单列，因为它已经被包含在上面两支里了——删掉
s1[i]之后，子问题dp[i+1][j]内部仍可以选择删掉s2[j]。这是这类双序列 DP 中一个很容易被质疑、也很值得主动向面试官解释的点。
解题步骤
- 开一个
(m+1) × (n+1)的二维数组：多出来的那一行一列专门存「某一侧已经走空」的基准状态，这样主循环里不需要任何越界判断。- 先填最后一列
dp[i][n]：从i = m-1倒着累加s1.charAt(i)，含义是s2空了、s1[i:]必须全删。倒着填是因为dp[i][n]依赖dp[i+1][n]，被依赖的那一格必须先算好。- 再填最后一行
dp[m][j]：对称地累加s2.charAt(j)。注意dp[m][n]保持 0，Java 与 Go 的数组默认值恰好就是 0，不需要显式赋值。- 双重循环，两层都从大到小：因为
dp[i][j]依赖dp[i+1][j+1]、dp[i+1][j]、dp[i][j+1]，三个依赖项的下标都不小于当前，所以必须倒序枚举才能保证读到的都是已经算好的值。- 字符相等时直接继承
dp[i+1][j+1]：不加任何代价。这里不需要再和「删一个」的方案比较，因为删除只会增加代价、不会减少。- 字符不等时取两支的最小值：
del1 = s1.charAt(i) + dp[i+1][j]、del2 = s2.charAt(j) + dp[i][j+1]。Java 里char参与加法会自动提升为int，得到的正是 ASCII 值；Go 里s1[i]是byte，必须显式int(...)转换后再相加。- 返回
dp[0][0]：两个完整串的答案。以
s1 = "sea"、s2 = "eat"走一遍（s=115、e=101、a=97、t=116，m = n = 3）。先填基准。最后一列自下而上：
dp[3][3] = 0，dp[2][3] = 97（删a），dp[1][3] = 97 + 101 = 198（删ea），dp[0][3] = 198 + 115 = 313（删sea）。最后一行同理：dp[3][2] = 116，dp[3][1] = 116 + 97 = 213，dp[3][0] = 213 + 101 = 314。主循环从
i = 2开始。i = 2（s1[2] = 'a'）：j = 2时'a'与't'不等，del1 = 97 + dp[3][2] = 213、del2 = 116 + dp[2][3] = 213，dp[2][2] = 213；j = 1时'a'与'a'相等，dp[2][1] = dp[3][2] = 116；j = 0时'a'与'e'不等，del1 = 97 + dp[3][0] = 411、del2 = 101 + dp[2][1] = 217，dp[2][0] = 217。
i = 1（s1[1] = 'e'）：j = 2时不等，del1 = 101 + dp[2][2] = 314、del2 = 116 + dp[1][3] = 314，dp[1][2] = 314；j = 1时'e'与'a'不等，del1 = 101 + dp[2][1] = 217、del2 = 97 + dp[1][2] = 411，dp[1][1] = 217；j = 0时'e'与'e'相等，dp[1][0] = dp[2][1] = 116。
i = 0（s1[0] = 's'）：j = 0时's'与'e'不等，del1 = 115 + dp[1][0] = 231、del2 = 101 + dp[0][1]。而dp[0][1]需要先算出来：j = 1时's'与'a'不等，del1 = 115 + dp[1][1] = 332、del2 = 97 + dp[0][2]；j = 2时's'与't'不等，del1 = 115 + dp[1][2] = 429、del2 = 116 + dp[0][3] = 429，故dp[0][2] = 429，于是dp[0][1] = min(332, 97 + 429) = 332，最后dp[0][0] = min(231, 101 + 332) = 231。答案 231 = 115 + 116，也就是删掉
s1的's'和s2的't'，两边都变成"ea"，与题目样例一致。
代码实现
class Solution {
// 若字符相等则继承 dp[i+1][j+1]，否则取删除一边的最小代价。
public int minimumDeleteSum(String s1, String s2) {
int m = s1.length();
int n = s2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = m - 1; i >= 0; i--) {
dp[i][n] = dp[i + 1][n] + s1.charAt(i);
}
for (int j = n - 1; j >= 0; j--) {
dp[m][j] = dp[m][j + 1] + s2.charAt(j);
}
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
if (s1.charAt(i) == s2.charAt(j)) {
dp[i][j] = dp[i + 1][j + 1];
} else {
int del1 = s1.charAt(i) + dp[i + 1][j];
int del2 = s2.charAt(j) + dp[i][j + 1];
dp[i][j] = Math.min(del1, del2);
}
}
}
return dp[0][0];
}
}
func minimumDeleteSum(s1 string, s2 string) int {
// 若字符相等则继承 dp[i+1][j+1]，否则取删除一边的最小代价。
m := len(s1)
n := len(s2)
dp := make([][]int, m+1)
for i := 0; i <= m; i++ {
dp[i] = make([]int, n+1)
}
for i := m - 1; i >= 0; i-- {
dp[i][n] = dp[i+1][n] + int(s1[i])
}
for j := n - 1; j >= 0; j-- {
dp[m][j] = dp[m][j+1] + int(s2[j])
}
for i := m - 1; i >= 0; i-- {
for j := n - 1; j >= 0; j-- {
if s1[i] == s2[j] {
dp[i][j] = dp[i+1][j+1]
} else {
del1 := int(s1[i]) + dp[i+1][j]
del2 := int(s2[j]) + dp[i][j+1]
if del1 < del2 {
dp[i][j] = del1
} else {
dp[i][j] = del2
}
}
}
}
return dp[0][0]
}
复杂度分析
- 时间复杂度：$O(mn)$，其中 $m$、$n$ 是两个字符串的长度。状态总数是 $(m+1)(n+1)$，每个状态的转移只做常数次比较与加法，不存在重复计算。
- 空间复杂度：$O(mn)$，二维 dp 表按原样保留。由于
dp[i][j]只依赖第i行与第i+1行，可以滚动成两行把空间压到 $O(n)$，但二维写法状态含义更直白，调试时能直接打印整张表，面试中通常先写二维再口头说明可以滚动。
关键点总结
- 双序列问题的通用套路是两个下标各占一维，状态定义写成「前缀/后缀对」的最优值；能把这句话说清楚，编辑距离、最长公共子序列、交错字符串都是同一个模板。
- 本题与最长公共子序列的差别在于代价带权：目标不是保留最多字符，而是保留 ASCII 总和最大的公共子序列，等价地就是删掉总和最小的部分。面试时被问「和 1143 有什么区别」，答这一句即可。
- 「首字符相等就一定配对」这个贪心结论要能证明：保留它不产生代价，也不会削弱剩余子问题的可选空间，所以不存在更优的替代方案。
- 转移里不需要单列「两个都删」的分支，它已被两个单删分支的后续递归覆盖；识别出哪些分支是冗余的，能让转移方程更精简也更不易写错。
- dp 的循环方向必须与依赖方向相反：依赖
i+1、j+1就要倒序枚举。写 dp 前先看一眼转移方程里的下标偏移，是避免读到脏值的最简单办法。
易错点总结
- 直接照搬最长公共子序列的答案：先求出 LCS 再把其余字符的 ASCII 相加，在
s1 = "az"、s2 = "za"这类用例上就会出错——LCS 长度都是 1，但保留z（122）显然比保留a（97）省得多，必须按权值而非长度做最优化。- 基准状态只置
dp[m][n] = 0，其余留 0：s1 = "a"、s2 = "b"时，dp[1][0]本该是 98 却是 0，转移会算出dp[0][0] = min(97+0, 98+0) = 97，漏掉了另一侧的删除代价，正确答案是 195。- 循环写成正序
for i = 0..m-1：dp[i][j]会去读还没赋值的dp[i+1][j+1]，整张表退化成一堆 0，"sea"/"eat"会返回 0。- Go 里忘记
int(s1[i])转换：s1[i]是byte，byte + int直接编译不过；即使强行用byte累加，"zzz"这类输入的总和 366 也会在 255 处回绕。- 字符相等时仍去比较删除分支：写成
dp[i][j] = min(dp[i+1][j+1], s1[i]+dp[i+1][j], ...)虽然不会算错，但把「相等必配对」的结论丢了，面试官追问为什么可以直接继承时容易答不上来。- 数组开成
new int[m][n]：少了基准行列，dp[i+1][j+1]在i = m-1时立刻越界，"a"/"b"就会抛异常。- 把
Math.min写成Math.max："sea"/"eat"会返回 429 这类明显偏大的值，而在两个完全不同的短串上又可能碰巧相同，不易被弱用例发现。- 误以为最终要把两串都删空：
s1 = "ab"、s2 = "ab"时若按「全删」计算会返回 2×(97+98)=390，而正确答案是 0，两串本来就相等，一个字符都不用删。- 用
s1.charAt(i) - 'a'当作代价：题目要的是 ASCII 原值不是字母序号，"a"/"b"会得到 1 而不是 195。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 1143. 最长公共子序列 | 中等 | 同一转移骨架但代价不带权，目标改成保留字符数最多 |
| 583. 两个字符串的删除操作 | 中等 | 每次删除代价固定为 1，答案等于 m + n - 2 × LCS
|
| 72. 编辑距离 | 中等 | 除删除外还允许插入与替换，转移多一支 dp[i+1][j+1] + 1
|
| 1035. 不相交的线 | 中等 | 换皮的最长公共子序列，难点是识别「连线不相交」等价于保序匹配 |
| 97. 交错字符串 | 中等 | 状态存布尔可达性而非最优值，两串按顺序拼成第三串 |
| 115. 不同的子序列 | 困难 | 求方案数，字符相等时两支要相加而不是取最优 |
| 392. 判断子序列 | 简单 | 单向匹配，双指针贪心即可，$O(m+n)$ 优于 DP |
| 516. 最长回文子序列 | 中等 | 单串与自身逆序做 LCS，也可直接用区间 DP 写 |
| 1092. 最短公共超序列 | 困难 | 在 LCS 的 dp 表上回溯构造具体字符串，而不只是返回一个数值 |