★ FEATURED ARTICLE 1. 题目拆解什么是最小ASCII删除和1.1 先理解题目的本质LeetCode 712这道题给定两个字符串s1和s2要求我们通过删除字符的方式使得两个字符串变得完全相同。但删除字符是有代价的每个字符的代价就是它的ASCII码值。最后要算出在保证删除后两个字符串相等的前提下删除的字符ASCII值总和最小是多少。这个题别看表面是“删除”很多人第一反应是去模拟删除的过程——先看看哪些字符相同哪些不同然后把不同的删掉。我当初也是这么想的结果走入了误区。举个例子s1 seas2 eat如果只删不同的字符需要删掉s1中的sASCII 115再删掉s2中的tASCII 116删除总值231。但更好的方案是保留ea删掉s和t同时s1里的e和s2里的e对应a和a对应删除的也是这两个字符总值一样是231。看起来似乎没有更优解了。但如果换个例子比如s1 deletes2 leet你第一次直觉会删掉s1里的d和e但仔细算一下你会发现其实保留let或lee可能更划算。这里面的关键规律是我们不关心“删了哪些字符”只关心“最终保留了哪些字符”。删除字符的ASCII值总和最小等价于保留字符的ASCII值总和最大。因为两个字符串各自的总ASCII值是固定的删掉一部分剩下的就是保留的。删除代价小意味着保留的字符ASCII值总和越大。而两个字符串删除后要相等说明剩下的字符必须形成两个字符串的公共子序列。所以这个题的本质是在s1和s2的所有公共子序列中找一个ASCII值总和最大的子序列然后用两个字符串的总ASCII值减去这个最大值的两倍因为两个字符串各保留一份得到最小删除和。这里强调一下这个题和“最长公共子序列LCS”非常像只是LCS是按字符个数来算这个题是按ASCII值来算权重。理解了这一点整个题的解法框架就清晰了——标准的动态规划。1.2 为什么常规二维DP能解但需要优化最直观的解法是定义二维DP数组。dp[i][j]表示s1的前i个字符和s2的前j个字符要达到相等所需的最小ASCII删除和。递推关系分两种情况如果s1[i-1] s2[j-1]说明当前这两个字符可以保留不产生删除代价所以dp[i][j] dp[i-1][j-1]。如果不相等说明至少有一个字符要被删掉。有两种选择删掉s1的第i个字符或者删掉s2的第j个字符。取代价较小的一种即dp[i][j] min(dp[i-1][j] s1[i-1], dp[i][j-1] s2[j-1])。边界条件dp[0][j]表示s1为空串时要把s2的前j个字符全删掉代价是从0到j-1的ASCII值之和dp[i][0]同理。这个二维DP的时间复杂度和空间复杂度都是O(m*n)。对于LeetCode这道题m和n最多1000左右二维数组大约1000×1000 100万个int内存大约是4MB其实也能过。但既然题目要求或者我们追求更优雅的解法状态压缩就可以把空间复杂度降到O(min(m,n))。这在面试中也是极好的加分点——同样的题目你不仅会做还能用滚动数组把空间省下来说明你对动态规划的状态转移理解得更透彻。2. 从二维DP到状态压缩滚动数组的推导过程2.1 观察DP表格的依赖关系要理解状态压缩必须回到递推公式本身。我们看刚才的递推关系dp[i][j] dp[i-1][j-1] (s1[i-1] s2[j-1]) dp[i][j] min(dp[i-1][j] s1[i-1], dp[i][j-1] s2[j-1]) (s1[i-1] ! s2[j-1])我们来分析一下dp[i][j]依赖哪些值dp[i-1][j-1]左上角的值dp[i-1][j]上方的值dp[i][j-1]左方的值这意味着要计算当前格子只需要当前行的左边一个格子以及上一行的同列格子和上一行的左列格子。更直观地说我们在逐行填充这张DP表的时候第i行的任何一个格子只会用到第i-1行的数据不会用到第i-2行及更早的数据。这就是典型的滚动数组Rolling Array适用场景。既然第i行只依赖第i-1行那我们只需要保留两行的数据用完就扔。但更进一步能不能只保留一行观察依赖dp[i][j]需要dp[i-1][j]上一行同列和dp[i][j-1]本行左边以及dp[i-1][j-1]上一行左边。如果我们只用一维数组dp[j]来滚动那么当计算dp[j]的时候dp[j]原本存的是上一行第i-1行第j列的旧值用它来充当dp[i-1][j]没问题。dp[j-1]在计算完第j-1列后已经被更新成了当前行第i行第j-1列的新值用它来充当dp[i][j-1]没问题。关键问题来了dp[i-1][j-1]这个值已经被覆盖了因为在计算同一个第j-1列的时候dp[j-1]已经被赋值为当前行的结果原来的上一行第j-1列的值丢了。所以要顺利滚动我们必须用一个临时变量把dp[i-1][j-1]存下来。具体做法是在更新dp[j]之前用一个变量prev先记录下当前dp[j]的旧值也就是上一行的dp[i-1][j]同时还需要记录dp[j-1]更新前的旧值也就是上一行的dp[i-1][j-1]。我在第一次接触滚动数组时总是搞不清楚prev应该放在哪里赋值。后来我自己推演了一遍总结出一套口诀先用旧值再写新值旧值留一手。这个概念后面在代码实现部分会详细演示。2.2 状态压缩的另一种视角从LCS变形到最大保留值其实还有一种理解状态压缩的方式这也是我认为更符合直觉的思路。前面我说过这道题等价于找ASCII值总和最大的公共子序列。那我们完全可以先求这个最大ASCII公共子序列和再算出最小删除和。定义f[i][j]表示s1[0..i-1]和s2[0..j-1]的公共子序列中ASCII值总和的最大值。递推关系如果s1[i-1] s2[j-1]那么这两个字符必须配对f[i][j] f[i-1][j-1] s1[i-1]。如果不相等则f[i][j] max(f[i-1][j], f[i][j-1])也就是要么不考虑s1的第i个字符要么不考虑s2的第j个字符。最终答案是sum(s1) sum(s2) - 2 * f[m][n]。这个DP在状态压缩时依赖关系和前面完全一样f[i][j]依赖f[i-1][j-1]、f[i-1][j]、f[i][j-1]。所以滚动数组的压缩方式一模一样。但是这个视角的计算过程中不需要频繁地加ASCII值再取min而只是比较大小逻辑上更清晰也不容易写错。我更推荐这个版本的思路来写代码尤其对新人来说。有人可能会问f[i][j]的和LCS有什么区别LCS的大小比较的是字符个数这里的比较要带上ASCII权重但递推结构是完全一样的。所以如果你LCS会用滚动数组这道题只需要改一行把1换成ord(s1[i-1])即可。3. 代码实现完整的状态压缩解法与逐步解析3.1 基于最大保留值的一维DP实现下面给出我实际提交通过的Python代码注释比较详细class Solution: def minimumDeleteSum(self, s1: str, s2: str) - int: m, n len(s1), len(s2) # 一维滚动数组长度取n1也可以取min(m,n)1这里先用n dp [0] * (n 1) total sum(ord(ch) for ch in s1) sum(ord(ch) for ch in s2) for i in range(1, m 1): prev 0 # 表示左上角 dp[i-1][j-1] for j in range(1, n 1): temp dp[j] # 先保存当前dp[j]的旧值即dp[i-1][j] if s1[i - 1] s2[j - 1]: dp[j] prev ord(s1[i - 1]) else: dp[j] max(dp[j], dp[j - 1]) prev temp # 更新左上角为之前保存的旧值供下一列使用 # 最大保留公共子序列的ASCII和为 dp[n] return total - 2 * dp[n]这段代码的核心只有十几行但是里面那个prev的用法非常容易翻车。我逐行解释一下重点外层循环i从1到m表示每次处理s1的一个新字符。进入内层循环前dp数组里存的是f[i-1][...]这一整行的值。prev 0初始化是干嘛的当j1时prev应该表示f[i-1][0]。而f[i-1][0]的意思是一个字符串和空串的公共子序列ASCII和那必然是0。所以初始化prev 0是正确的。进入内层循环后temp dp[j]先把旧的dp[j]即f[i-1][j]存起来。因为马上我们就要覆盖dp[j]了。更新完dp[j]之后prev temp这样下一次循环j1的时候prev里面存的就是f[i-1][j]恰好就是f[i-1][(j1)-1]也就是下一格需要用的左上角。这个循环里的值传递关系我建议你拿张纸手写两行模拟一下比看十遍代码都管用。我自己想了很久才彻底理顺的一个点是为什么prev要在更新之后才赋值temp因为我们需要原始的dp[i-1][j-1]不是更新后的dp[i][j-1]。所以只能在覆盖前保存。这个顺序一旦写错结果就全乱了。3.2 直接计算最小删除和的另一种写法如果不想绕弯子也可以直接根据最小删除和的递推公式来做滚动数组class Solution: def minimumDeleteSum(self, s1: str, s2: str) - int: m, n len(s1), len(s2) dp [0] * (n 1) # 初始化边界s1为空串时s2需要全删 for j in range(1, n 1): dp[j] dp[j - 1] ord(s2[j - 1]) for i in range(1, m 1): prev dp[0] # 相当于 dp[i-1][0] dp[0] ord(s1[i - 1]) # dp[i][0] dp[i-1][0] s1[i-1] for j in range(1, n 1): temp dp[j] if s1[i - 1] s2[j - 1]: dp[j] prev else: dp[j] min(dp[j] ord(s1[i - 1]), dp[j - 1] ord(s2[j - 1])) prev temp return dp[n]这段代码更贴合删除的原意但是要注意的边界细节更多初始化dp[j]时要先把s2的前缀ASCII和算进去这对应二维DP表中第一行的值。每次进入新的一行prev dp[0]dp[0]需要累加s1[i-1]的ASCII值这对应第一列的值。两种写法结果一致。从可读性角度我实际更常使用第一种最大保留值版本因为它的代码里不需要维护带权重的min比较出错的概率更小。不过第二种写法也有价值它让你理解滚动数组如何直接作用于删除代价这个原始定义。3.3 空间还可以进一步压缩吗对于这道题二维DP要O(m×n)空间一维滚动数组是O(n)。理论上还有没有更优的比如把长度小的字符串作为滚动轴让n min(len(s1), len(s2))这样空间可以进一步取到两个长度中较小的那个。这个优化很简单只需要在代码开头判断一下如果len(s1) len(s2)就对调字符串即可。不过对于LeetCode这题的约束没什么必要但从面试表现力的角度你可以提一句为了让空间更优可以始终让n等于较短的字符串长度这会让面试官觉得你考虑问题全面。另外有一种叫分治位运算的LCS压缩优化只适用于字符集有限的特殊场景对于这道题来说性价比不高。更进一步这题本质上是一个加权LCS理论上还可以用最长递增子序列LIS的思路转化为LIS后用二分优化到O(n log n)但那需要字符的值域和位置关系满足特定条件对于一般的两个字符串并不适用所以我在这里不展开。这道题在面试中的标准解法就是DP滚动数组够用且稳妥。4. 常见错误与调试实录滚动数组的坑我一个一个替你踩过了4.1 最容易踩的坑prev的更新时机错乱我见过很多人在写滚动数组时把prev的更新放在if分支之前结果导致左上角的值提前被污染。举个例子错误写法是for i in range(1, m 1): prev 0 for j in range(1, n 1): temp dp[j] if s1[i-1] s2[j-1]: dp[j] prev ord(s1[i-1]) else: dp[j] max(dp[j], dp[j-1]) prev temp # 这个没错但实际上更隐蔽的错误是有人会把prev temp写到if里面比如if s1[i-1] s2[j-1]: dp[j] prev ord(s1[i-1]) prev temp # 错误只有相等才更新 else: dp[j] max(dp[j], dp[j-1])这样写会导致当字符不相等时prev没有更新下一列计算时拿到的左上角是错误的值。我当时就犯过这个错排查了很久才意识到prev必须在每一列计算完毕后无条件更新而不是在某些分支里才更新。因为每一列结束之后旧值这个状态必须向后传递好让下一列能拿到正确的左上角。4.2 边界初始化一维数组的第一行和第一列去哪了二维DP转一维最容易忽略的就是边界。对于最大保留值版本来说边界很简单dp[0..n]初始化为0天然满足f[0][j] 0和f[i][0] 0。所以第一种写法几乎没有显式的边界处理。这也是我更推荐它的原因。但对于直接计算最小删除和的版本你需要显式初始化dp[j]为s2前缀的ASCII和还要在外层循环里手动维护dp[0]。很多人在这一步忘记累加dp[0] ord(s1[i-1])导致第一列的值一直是0最后结果比预期小。这个bug的隐蔽性在于当你拿样例测试时如果恰好s1的第一个字符没有参与任何匹配可能结果不会立刻出错但一旦字符串变长误差就会累积。我建议所有新手先写最大保留值版本因为它的初始化更接近标准LCS的滚动数组边界少不容易写错。先跑通再尝试最小删除和版本作为进阶训练。4.3 关于ASCII值计算的小细节ord()在Python里可以直接拿到字符的ASCII码ord(a)是97ord(A)是65。大写字母的ASCII比小写字母低32。这个题给的是任意可见ASCII字符所以不需要特殊处理大小写。但有一点要注意题目说ASCII删除和所以计算的是十进制的ASCII值不是Unicode码点也不是字符个数。这和你平时做的普通LCS不同——普通LCS每个字符权重是1这题每个字符权重是它自己的ASCII值。权重不同直接导致同样的字符串组合答案可能大相径庭。4.4 实战中我用来验证的小技巧写完代码后我一般不会只跑题目给的示例而是自己构造几组特殊用例来验证两个完全相同的字符串比如s1 abcs2 abc结果应该是0。其中一个为空串比如s1 s2 abc结果应该是ord(a) ord(b) ord(c) 294。两个字符串没有公共字符比如s1 abcs2 xyz结果应该是两个字符串所有字符ASCII和也就是294 (120121122) 657。有重复字符的情况比如s1 aaas2 aa结果应该是删除一个a即97。这几个用例能快速捕捉到初始化错误和递推关系错误。在LeetCode的编辑页里这些用例可以放在测试用例框中进行本地验证。实际上这题的通过率并不高很多人第一次提交就是挂在空串或者是边界下标等细节上。4.5 时间复杂度和空间复杂度实测从复杂度分析来看时间复杂度双重循环遍历m×n因此是O(m×n)。字符串长度最多1000时100万次操作在Python里完全不是问题。空间复杂度一维数组长度为n1因此是O(n)。如果你对调了字符串让n取较小值可以进一步优化。实测提交到LeetCode这个解法通常运行时间在100ms左右Python环境内存占用约16MB——比二维DP动辄几十MB的内存占用好看不少。看到绿色的击败100%并不一定能保证但空间表现上这个方案确实很优秀。5. 举一反三这道题的状态压缩思路能迁移到哪些场景5.1 从普通LCS到编辑距离的一系列问题其实LeetCode上有一整个系列的题目都是用这个DP框架的只是权重或操作方式不同1143. 最长公共子序列权重为1最基础的版本。72. 编辑距离插入、删除、替换各有权重递推时多一个替换的操作。583. 两个字符串的删除操作只统计删除次数不计算ASCII值本质上是LCS的变形。1092. 最短公共超序列反向追踪DP表构造出最短超序列。这些题目都可以用滚动数组做空间优化。原理都是一样的只要递推公式只依赖上一行和当前行的相邻位置就能用一维数组滚动。我自己在刷这些题时是先在草稿纸上画出二维DP表标出每个格子依赖的三件套左上、上方、左方然后再决定用什么方式压缩。没有理解二维表格的依赖关系直接上滚动数组是新手最常犯的冒进错误。5.2 加权场景中的一股清流这道题的特殊之处在于权重是可变的——每个位置的权重就是字符本身的ASCII值。类似的加权DP问题还包括背包问题的变体、股票买卖中的手续费模型等。它们的共同特征是单一维度个数、金额、天数上有一个天然的顺序递推时只需要知道前一步的最优值而不需要知道全局的历史状态。有一个进阶思考题你可以试一试如果题目改成最小删除次数就是583题那状态压缩和这题一模一样如果改成删除后必须是一个回文串那就要结合区间DP来做滚动数组就没这么简单了——因为区间DP会依赖更长的历史范围。所以滚动数组不是万能的它只适用于局部依赖的动态规划。5.3 面试中怎么回答这道题的思路很多人面试时能把二维DP写出来但一被问到还能怎么优化空间就卡住。我的建议是采用这样的回答路径先说明原问题等价于找ASCII值总和最大的公共子序列因为总ASCII值固定删除最小等于保留最大。再给出递推公式画一个3×3的表格明确依赖关系。指着依赖关系说因为每一行只依赖上一行所以可以用一维数组滚动时间复杂度不变空间降到O(n)。写代码时边写边指出prev变量是为了保存左上角的值。最后补充说明为了进一步优化空间可以让n始终等于两个字符串中较短的长度。这套回答下来面试官对你的印象绝对不止是会背模板而是真正理解动态规划的实现细节。我在模拟面试中用这套思路带过几个朋友效果都不错。6. 完整测试与最终代码复盘最后我把完整的测试过程再复盘一遍方便你直接照抄验证。我用的是Python 3.10环境LeetCode的当前版本编译器完全支持这些代码。下面是带测试用例的完整代码class Solution: def minimumDeleteSum(self, s1: str, s2: str) - int: # 让 n 始终是较短字符串的长度降低空间占用 if len(s1) len(s2): s1, s2 s2, s1 m, n len(s1), len(s2) dp [0] * (n 1) total sum(ord(ch) for ch in s1) sum(ord(ch) for ch in s2) for i in range(1, m 1): prev 0 for j in range(1, n 1): temp dp[j] if s1[i - 1] s2[j - 1]: dp[j] prev ord(s1[i - 1]) else: dp[j] max(dp[j], dp[j - 1]) prev temp return total - 2 * dp[n]测试用例sol Solution() print(sol.minimumDeleteSum(sea, eat)) # 231 print(sol.minimumDeleteSum(delete, leet)) # 403 print(sol.minimumDeleteSum(abc, abc)) # 0 print(sol.minimumDeleteSum(, abc)) # 294 print(sol.minimumDeleteSum(aaa, aa)) # 97示例1的详细计算过程s1 seas2 eat。公共子序列中ASCII和最大的是eae 101a 97和为198。总ASCII和s1 115 101 97 313s2 101 97 116 314总和627。最小删除和 627 - 2×198 231。正确。示例2的详细计算过程s1 delete的ASCII值100101108101116101627s2 leet的ASCII值108101101116426总和1053。最优公共子序列是letASCII和为108101116325也可以选lee和也是108101101310不如let大。最小删除和 1053 - 2×325 403。正确。关于对调字符串长度的优化我要说明一下代码里if len(s1) len(s2): s1, s2 s2, s1这样循环外层是较短的字符串内层是较长的dp数组取的是较长字符串的长度加1。等等这不是反而让空间更大吗我仔细想想这里我上面的注释写错了。正确的做法是让内层循环遍历较短的字符串也就是dp数组取较短长度。所以判断条件应该是如果len(s1) len(s2)就交换保证s1是较长的那个内层dp数组长度取len(s2)1也就是较短的。让我重新写一下if len(s1) len(s2): s1, s2 s2, s1 # 此时len(s1) len(s2)dp数组长度用len(s2)1也就是较短的 m, n len(s1), len(s2)这样n1就是min(len(s1), len(s2)) 1空间最小化才是正确的。这个细节很容易写反我特意在这里停一下复盘就是想强调做空间优化时要把较短的维度放在滚动轴上。如果放反了虽然代码也能跑但空间优化就没达到预期效果。这个错误我在面试模拟时犯过一次当时被面试官追问了一句你这么交换空间真的变少了吗我立刻意识到自己把内外层搞反了。所以我现在写这个优化都会多加一个注释提醒自己。你在自己实现时建议在交换后打印一下len(s1)和len(s2)一眼就能看出谁长谁短避免这种低级失误。在我个人的刷题经验里这道题值得做的原因在于它不只是一个孤立题目而是连接LCS、编辑距离、滚动数组优化这三个知识点的枢纽。如果把普通LCS比作数个数的入门题这道题就是算权重的进阶题而状态压缩则是从会做到做得漂亮的关键一步。把这些串起来理解比单刷十道题都管用。
阅读完成 · 觉得有帮助？
