题目描述
思路解析动画文字版
一句话套路:相同就抄左上角,不同就删一个、取较小。下面逐格填表套这条规则。
先看这张表的骨架:列头是 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题