题目描述
思路解析
一句话答案：LeetCode 712 两个字符串的最小 ASCII 删除和用二维 DP：dp[i][j] 是让两前缀相等的最小删代价，相同抄左上角、不同删 s1 或 s2 取较小，按 ASCII 加权非数量，时间 O(mn)、空间 O(n)。
删字符让两串相等，为什么代价按 ASCII 算
给两个字符串 s1、s2，只能删字符让它们变成完全一样，每删一个字符付出它的 ASCII 值（每个字符对应的数字编号，如 a=97）作代价，求最小总代价。关键是被删字符的 ASCII 之和最小、不是删的个数最少。
为什么不能先求最长公共子序列、其余全删
最直接是枚举「留哪些字符」：两串各留一个子序列（可不连续）使之相等、其余全删。可长 m、n 的串子序列有 2^m、2^n 种，指数爆炸跑不完。
留下的必是公共子序列，留最长的不就删得最少？但本题代价按 ASCII 加权：保留字符的 ASCII 权重和才决定省多少、不看个数，最长的未必最省。不如直接对删除代价做动态规划（DP，存子问题避免重算）。
dp[i][j] 存的是哪两段前缀的最小删代价
定义 dp[i][j] 为「让 s1 前 i 个字符和 s2 前 j 个字符相等的最小删除代价」，答案是 dp[m][n]。开 (m+1)×(n+1) 的表，第 0 行、第 0 列代表某串取空串：dp[0][0]=0；某串空时另一串只能全删，dp[i][0] 是 s1 前 i 个的 ASCII 前缀和，dp[0][j] 同理。
字符相同为什么抄左上角、不同为什么取两个方向的较小
算 dp[i][j] 看 s1 第 i 个字符 a、s2 第 j 个字符 b。相同时 a、b 都留、谁都不删，代价等于各砍掉这一字符后的子问题 dp[i-1][j-1]，直接抄左上角、不加 ASCII。
不同时至少删一个。删 a 是 ord(a)（取 a 的 ASCII 值）加 dp[i-1][j]，删 b 是 ord(b) 加 dp[i][j-1]，取较小：dp[i][j]=min(dp[i-1][j]+ord(a), dp[i][j-1]+ord(b))。相同却加 ASCII 会多算，只看一个方向会漏掉更省的删法。
拿 sea 和 eat 把这张表填出 231
ASCII：s=115、e=101、a=97、t=116。边界第 0 列 dp[1..3][0]=115、216、313，第 0 行 dp[0][1..3]=101、198、314。
s 对 e、a、t 都不同，首格显式算一次：dp[1][1]=min(dp[0][1]+115, dp[1][0]+101)=216，之后压缩写 dp[1][2]=313、dp[1][3]=429。第 2 个 e 对 e 相同，抄 dp[1][0]=115；e 对 a 取 min(414,212)=212，e 对 t 取 min(530,328)=328。第 3 个 a 对 e 得 212，a 对 a 相同抄 dp[2][1]=115，a 对 t 取 min(425,231)=231，右下角 dp[3][3]=231。
空串边界怎么铺，无公共字符时代价是多少
整张表 (m+1)(n+1) 格、每格 O(1) 转移，时间 O(m×n)；dp[i][j] 只依赖正上、正左、左上角，滚动数组只留一行把空间压到 O(n)。两个边界：某串为空则另一串全删，代价是它的 ASCII 总和；两串毫无公共字符则各自删空，答案是两串 ASCII 总和相加。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
一句话套路:相同就抄左上角,不同就删一个、取较小。下面逐格填表套这条规则。
先看这张表的骨架:列头是 s2「eat」的字符、行头是 s1「sea」的字符,左上再各加一行一列代表「空串」。dp[i][j] 就是「s1 前 i 个 与 s2 前 j 个相等」的最小删除代价,现在全是「·」表示还没算。
先建一张 (m+1)×(n+1) 的表。左上角 dp[0][0]=0:两个都是空串,本来就相等,删 0 个、代价 0(紫格)。
第 0 列:s2 是空串,要让 s1 前 1 个字符也变空,只能全删。dp[1][0] = 上一格 0 再加上 "s" 的 ASCII 115 = 115(紫格,蓝格是它依赖的上一行)。
第 0 列:s2 是空串,要让 s1 前 2 个字符也变空,只能全删。dp[2][0] = 上一格 115 再加上 "e" 的 ASCII 101 = 216(紫格,蓝格是它依赖的上一行)。
第 0 列:s2 是空串,要让 s1 前 3 个字符也变空,只能全删。dp[3][0] = 上一格 216 再加上 "a" 的 ASCII 97 = 313(紫格,蓝格是它依赖的上一行)。
第 0 行:s1 是空串,要让 s2 前 1 个字符变空,同样全删。dp[0][1] = 左边一格 0 加 "e" 的 ASCII 101 = 101(紫格,蓝格是它依赖的左邻)。
第 0 行:s1 是空串,要让 s2 前 2 个字符变空,同样全删。dp[0][2] = 左边一格 101 加 "a" 的 ASCII 97 = 198(紫格,蓝格是它依赖的左邻)。
第 0 行:s1 是空串,要让 s2 前 3 个字符变空,同样全删。dp[0][3] = 左边一格 198 加 "t" 的 ASCII 116 = 314(紫格,蓝格是它依赖的左邻)。
比较 "s" 和 "e":不同,必须删掉其中一个。方案一删 s1 的 "s":上方格 dp[0][1]=101 加 115 = 216。方案二删 s2 的 "e":左边格 dp[1][0]=115 加 101 = 216。两个方案代价相同,都是 216;平局时任选其一都不影响最优值,本格填 216,填入紫格。
比较 "s" 和 "a":不同,必须删掉其中一个。方案一删 s1 的 "s":上方格 dp[0][2]=198 加 115 = 313。方案二删 s2 的 "a":左边格 dp[1][1]=216 加 97 = 313。两个方案代价相同,都是 313;平局时任选其一都不影响最优值,本格填 313,填入紫格。
比较 "s" 和 "t":不同,必须删掉其中一个。方案一删 s1 的 "s":上方格 dp[0][3]=314 加 115 = 429。方案二删 s2 的 "t":左边格 dp[1][2]=313 加 116 = 429。两个方案代价相同,都是 429;平局时任选其一都不影响最优值,本格填 429,填入紫格。
比较 "e"(s1 第 2 个)和 "e"(s2 第 1 个):相同!这个字符两边都能留着、谁都不用删。直接把左上角 dp[1][0]=115 抄过来填入紫格(蓝格就是左上角)。
比较 "e" 和 "a":不同,必须删掉其中一个。方案一删 s1 的 "e":上方格 dp[1][2]=313 加 101 = 414。方案二删 s2 的 "a":左边格 dp[2][1]=115 加 97 = 212。取较小 = 212(删 a更省),填入紫格。
比较 "e" 和 "t":不同,必须删掉其中一个。方案一删 s1 的 "e":上方格 dp[1][3]=429 加 101 = 530。方案二删 s2 的 "t":左边格 dp[2][2]=212 加 116 = 328。取较小 = 328(删 t更省),填入紫格。
比较 "a" 和 "e":不同,必须删掉其中一个。方案一删 s1 的 "a":上方格 dp[2][1]=115 加 97 = 212。方案二删 s2 的 "e":左边格 dp[3][0]=313 加 101 = 414。取较小 = 212(删 a更省),填入紫格。
比较 "a"(s1 第 3 个)和 "a"(s2 第 2 个):相同!这个字符两边都能留着、谁都不用删。直接把左上角 dp[2][1]=115 抄过来填入紫格(蓝格就是左上角)。
比较 "a" 和 "t":不同,必须删掉其中一个。方案一删 s1 的 "a":上方格 dp[2][3]=328 加 97 = 425。方案二删 s2 的 "t":左边格 dp[3][2]=115 加 116 = 231。取较小 = 231(删 t更省),填入紫格。
表填满了。沿转移回看:s1 的 "e"(第 2 个)和 s2 的 "e"(第 1 个)相同、"a" 与 "a" 相同,它们组成保留下来的公共子序列 "ea"(蓝格);其余 "s"、"t" 被删。
整张表填满,右下角 dp[3][3] = 231 就是答案:让 "sea" 和 "eat" 相等的最小删除代价。回看路径,正是删了 s1 的 "s"(115)和 s2 的 "t"(116),两边都剩 "ea",115 + 116 = 231。
复盘整条思路:dp[i][j] 表示「让两个前缀相等的最小删代价」,相同抄左上角、不同删一个取较小,从左上往右下一格格推到底,右下角即答案 231。
边界:有一方空则全删另一方;完全相同为 0;毫无公共字符则两串全删。
两个追问:它是带 ASCII 权重的 LCS;最大化的是权重和不是长度。
参考代码
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]复杂度
- 时间：O(mn)，m、n 为两串长度,每个格子 O(1) 转移,共填 m×n 个格子
- 空间：O(n)，滚动数组只存一行;若用完整二维表则是 O(mn)
易错点
面试追问把动画讲成自己的话
追问这题和最长公共子序列(LCS)是什么关系?
追问为什么这里要按 ASCII 之和而不是子序列长度来最大化?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最长重复子数组
LeetCode 718 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题