两个字符串的最小 ASCII 删除和 图解题解

这道题到底在问什么

输入

s1 = "sea", s2 = "eat"

输出

231(删掉 s1 的 s=115 和 s2 的 t=116,两边都剩 "ea")

输入

s1 = "delete", s2 = "leet"

输出

403(保留公共子序列 "let",删掉 s1 的 d、e、e 和 s2 多出的 e)

最优解：一步一步想明白

1. 3一句话套路:相同就抄左上角,不同就删一个、取较小。下面逐格填表套这条规则。
2. 4先看这张表的骨架:列头是 s2「eat」的字符、行头是 s1「sea」的字符,左上再各加一行一列代表「空串」。dp[i][j] 就是「s1 前 i 个 与 s2 前 j 个相等」的最小删除代价,现在全是「·」表示还没算。
3. 5先建一张 (m+1)×(n+1) 的表。左上角 dp[0][0]=0:两个都是空串,本来就相等,删 0 个、代价 0(紫格)。
4. 6第 0 列:s2 是空串,要让 s1 前 1 个字符也变空,只能全删。dp[1][0] = 上一格 0 再加上 "s" 的 ASCII 115 = 115(紫格,蓝格是它依赖的上一行)。
5. 7第 0 列:s2 是空串,要让 s1 前 2 个字符也变空,只能全删。dp[2][0] = 上一格 115 再加上 "e" 的 ASCII 101 = 216(紫格,蓝格是它依赖的上一行)。
6. 8第 0 列:s2 是空串,要让 s1 前 3 个字符也变空,只能全删。dp[3][0] = 上一格 216 再加上 "a" 的 ASCII 97 = 313(紫格,蓝格是它依赖的上一行)。
7. 9第 0 行:s1 是空串,要让 s2 前 1 个字符变空,同样全删。dp[0][1] = 左边一格 0 加 "e" 的 ASCII 101 = 101(紫格,蓝格是它依赖的左邻)。
8. 10第 0 行:s1 是空串,要让 s2 前 2 个字符变空,同样全删。dp[0][2] = 左边一格 101 加 "a" 的 ASCII 97 = 198(紫格,蓝格是它依赖的左邻)。
9. 11第 0 行:s1 是空串,要让 s2 前 3 个字符变空,同样全删。dp[0][3] = 左边一格 198 加 "t" 的 ASCII 116 = 314(紫格,蓝格是它依赖的左邻)。
10. 12比较 "s" 和 "e":不同,必须删掉其中一个。方案一删 s1 的 "s":上方格 dp[0][1]=101 加 115 = 216。方案二删 s2 的 "e":左边格 dp[1][0]=115 加 101 = 216。两个方案代价相同,都是 216;平局时任选其一都不影响最优值,本格填 216,填入紫格。
11. 13比较 "s" 和 "a":不同,必须删掉其中一个。方案一删 s1 的 "s":上方格 dp[0][2]=198 加 115 = 313。方案二删 s2 的 "a":左边格 dp[1][1]=216 加 97 = 313。两个方案代价相同,都是 313;平局时任选其一都不影响最优值,本格填 313,填入紫格。
12. 14比较 "s" 和 "t":不同,必须删掉其中一个。方案一删 s1 的 "s":上方格 dp[0][3]=314 加 115 = 429。方案二删 s2 的 "t":左边格 dp[1][2]=313 加 116 = 429。两个方案代价相同,都是 429;平局时任选其一都不影响最优值,本格填 429,填入紫格。
13. 15比较 "e"(s1 第 2 个)和 "e"(s2 第 1 个):相同!这个字符两边都能留着、谁都不用删。直接把左上角 dp[1][0]=115 抄过来填入紫格(蓝格就是左上角)。
14. 16比较 "e" 和 "a":不同,必须删掉其中一个。方案一删 s1 的 "e":上方格 dp[1][2]=313 加 101 = 414。方案二删 s2 的 "a":左边格 dp[2][1]=115 加 97 = 212。取较小 = 212(删 a更省),填入紫格。
15. 17比较 "e" 和 "t":不同,必须删掉其中一个。方案一删 s1 的 "e":上方格 dp[1][3]=429 加 101 = 530。方案二删 s2 的 "t":左边格 dp[2][2]=212 加 116 = 328。取较小 = 328(删 t更省),填入紫格。
16. 18比较 "a" 和 "e":不同,必须删掉其中一个。方案一删 s1 的 "a":上方格 dp[2][1]=115 加 97 = 212。方案二删 s2 的 "e":左边格 dp[3][0]=313 加 101 = 414。取较小 = 212(删 a更省),填入紫格。
17. 19比较 "a"(s1 第 3 个)和 "a"(s2 第 2 个):相同!这个字符两边都能留着、谁都不用删。直接把左上角 dp[2][1]=115 抄过来填入紫格(蓝格就是左上角)。
18. 20比较 "a" 和 "t":不同,必须删掉其中一个。方案一删 s1 的 "a":上方格 dp[2][3]=328 加 97 = 425。方案二删 s2 的 "t":左边格 dp[3][2]=115 加 116 = 231。取较小 = 231(删 t更省),填入紫格。
19. 21表填满了。沿转移回看:s1 的 "e"(第 2 个)和 s2 的 "e"(第 1 个)相同、"a" 与 "a" 相同,它们组成保留下来的公共子序列 "ea"(蓝格);其余 "s"、"t" 被删。
20. 22整张表填满,右下角 dp[3][3] = 231 就是答案:让 "sea" 和 "eat" 相等的最小删除代价。回看路径,正是删了 s1 的 "s"(115)和 s2 的 "t"(116),两边都剩 "ea",115 + 116 = 231。
21. 23复盘整条思路:dp[i][j] 表示「让两个前缀相等的最小删代价」,相同抄左上角、不同删一个取较小,从左上往右下一格格推到底,右下角即答案 231。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        n = len(s2)
        dp = [0] * (n + 1)
        for j, ch in enumerate(s2, 1):
            dp[j] = dp[j-1] + ord(ch)
        for a in s1:
            prev = dp[0]
            dp[0] += ord(a)
            for j, b in enumerate(s2, 1):
                old = dp[j]
                if a == b:
                    dp[j] = prev
                else:
                    dp[j] = min(dp[j] + ord(a), dp[j-1] + ord(b))
                prev = old
        return dp[n]

#include <algorithm>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int n = s2.size();
        vector<int> dp(n + 1);
        for (int j = 1; j <= n; ++j) dp[j] = dp[j-1] + s2[j-1];
        for (char a : s1) {
            int prev = dp[0];
            dp[0] += a;
            for (int j = 1; j <= n; ++j) {
                int old = dp[j];
                if (a == s2[j-1]) dp[j] = prev;
                else dp[j] = min(dp[j] + (int)a, dp[j-1] + (int)s2[j-1]);
                prev = old;
            }
        }
        return dp[n];
    }
};

import java.util.*;
class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int n = s2.length();
        int[] dp = new int[n + 1];
        for (int j = 1; j <= n; j++) dp[j] = dp[j - 1] + s2.charAt(j - 1);
        for (char a : s1.toCharArray()) {
            int prev = dp[0];
            dp[0] += a;
            for (int j = 1; j <= n; j++) {
                int old = dp[j];
                if (a == s2.charAt(j - 1)) dp[j] = prev;
                else dp[j] = Math.min(dp[j] + a, dp[j - 1] + s2.charAt(j - 1));
                prev = old;
            }
        }
        return dp[n];
    }
}

复杂度

面试官可能追问