动手做712这道题的时候我第一反应也是“这不就是最长公共子序列LCS的变种吗”。但真把两种写法都推完才发现解法二这种直接递推的思路反而更贴合题目本身的语义——不用绕一圈去算“保留了什么”而是直接盯着“删掉什么最便宜”。今天这篇就把解法二完整拆开从状态定义到转移方程从边界初始化到滚动数组优化最后把我在实际提交里踩过的坑一并摆出来。这道题适合两类人一类是刚学完动态规划、想找一道难度适中但能练熟状态定义的题目另一类是已经背过LCS模板、但一直没搞懂dp表格里每个格子到底是怎么填的人。如果你属于后者这一篇应该能帮你把最后那层窗户纸捅破。1. 题目到底在问什么1.1 输入输出与约束先明确需求。给定两个字符串s1和s2每次操作可以从任意一个字符串中删除一个字符代价是该字符的ASCII码值。要求最终两个字符串完全相等问最小删除代价总和是多少。注意一个关键点这里问的不是“最少删除几个字符”而是“删除字符的ASCII码值总和最小是多少”。这意味着字符的权重不一样删一个z122和删一个a97代价不同这对解题策略有直接影响。题目约束是字符串长度在1到1000之间字符为小写英文字母。全部字符ASCII码总和最高也就是1000 × 122 122000int类型完全能放下但这不代表我们不需要思考代价累积的问题——初始化时用前缀和累加正好把这个细节一起处理掉。1.2 两个示例带你找感觉先看经典示例s1 seas2 eat。s1 seas 115e 101a 97s2 eate 101a 97t 116最优策略是删除s1中的s代价115删除s2中的t代价116剩下ea和ea完全相等总代价115 116 231。有人可能会问为什么不删掉s1的e和s2的e保留sa和at因为那样剩下的字符串还是不相等还得继续删代价自然更高。这个例子说明我们真正要保留的是一对“公共子序列”而且这个子序列的ASCII值越大删除代价就越小。这也是解法一的出发点。再看一题比较有迷惑性的s1 deletes2 leet。s1 deleted100e101l108e101t116e101s2 leetl108e101e101t116我们保留let这个公共子序列。s1删掉d和两个e代价是100 101 101 302s2删掉多余的e代价是101。总代价403这就是最优解。这个例子有意思的地方在于s1里的let不是连续出现的它是d、e、l、e、t、e中间挑出来的l、e、t。这里提醒我们公共子序列不要求连续只看相对顺序。1.3 两种解法的关系解法一走的是“间接路线”先算出两个字符串的ASCII总和再算出ASCII值最大的公共子序列答案 总和 - 2 × 公共子序列的ASCII和。解法二走的是“直接路线”定义dp[i][j]为“让s1的前i个字符和s2的前j个字符变得完全相等所需的最小删除代价”然后直接递推。两种写法殊途同归但解法二的好处是不需要额外理解“LCS的ASCII值为什么等于保留代价”因为状态定义本身就长在题目要求上。2. 解题思路为什么直接递推更顺手2.1 解法一的思路与局限先简单说下解法一。定义lcs[i][j]为“s1前i个字符和s2前j个字符中ASCII值最大的公共子序列的ASCII和”转移方程是如果s1[i-1] s2[j-1]lcs[i][j] lcs[i-1][j-1] ord(s1[i-1])否则lcs[i][j] max(lcs[i-1][j], lcs[i][j-1])最后答案是sum1 sum2 - 2 * lcs[m][n]。这个方法本身没有错误但它有个认知门槛你得先想明白“保留的公共子序列ASCII值最大等价于删除代价最小”。这个等价关系在逻辑上确实成立因为被保留的字符两边都不扣分总代价就是两边ASCII总和减去两倍保留值。但问题也正在这里。很多人在实际写代码时只是机械地抄LCS模板压根没去推敲为什么要减两倍。一旦题目变形比如后面要加个“必须保留某些字符”的条件解法一就很难扩展。2.2 直接递推的思路解法二的核心思维是“看最后一个字符”。处理字符串的动态规划问题十有八九都可以从最后一个字符切入因为删除操作只能从字符串的两端或中间删但无论怎么删最终都要面对“当前比较到哪两个字符”的问题。具体到712这道题我们问的是s1的前i个字符和s2的前j个字符怎样才能变得相等先看s1[i-1]和s2[j-1]这两个字符如果它俩相等最优解中完全可以保留它们让它们成为最终相等字符串的一部分不需要为它们付出删除代价。如果它俩不相等那这两个字符不可能同时出现在最终的相等字符串里必须至少删掉其中一个。要么删s1[i-1]要么删s2[j-1]取代价更小的那一边。这个推理过程不需要依赖LCS的任何结论完全是从题目定义里长出来的所以实现起来更不容易出错。2.3 递推式的大致形状把上面的思路翻译成递推式if s1[i-1] s2[j-1]: dp[i][j] dp[i-1][j-1] else: dp[i][j] min( dp[i-1][j] ord(s1[i-1]), dp[i][j-1] ord(s2[j-1]) )这个递推式的形状和编辑距离72题、删除两个字符串的字符匹配583题非常像都是经典的字符串DP套路。有过这些题经验的人看到这个式子应该很眼熟没有经验的也不必担心下面一节会把每个细节掰开讲。3. 递推式逐项拆解3.1 状态定义dp[i][j] 的含义dp[i][j]表示让s1的前i个字符注意是长度i不是下标i和s2的前j个字符变得完全相等所需的最小删除ASCII代价。这里用长度而不是下标是为了方便处理空字符串。举个例子s1 seas2 eat那么dp[2][2]就表示让se和ea变得相等的最小代价。实际上se和ea都删掉一个字符后才能相等具体哪个方案最优由转移方程决定。这个状态定义直接对应题目的目标所以最终的答案就是dp[m][n]不需要再做任何额外转换。3.2 转移方程字符相等怎么办当i 0且j 0时我们比较s1的第i个字符s1[i-1]和s2的第j个字符s2[j-1]。如果它们相等比如都是e那么这两个字符没有理由被删除因为保留它们不会产生任何代价而且它们可以帮助两个字符串更快地变得相等。此时问题规模缩小为让s1的前i-1个字符和s2的前j-1个字符变得相等。所以dp[i][j] dp[i-1][j-1]这里有个初学者很容易犯的错认为既然字符相等就应该把这个字符的ASCII值也加上因为“留下了它”。但注意dp统计的是删除代价留下的字符不会产生删除代价所以这里绝不能再加ord(s1[i-1])。这个错误非常隐蔽一旦加了答案会明显偏大。3.3 转移方程字符不相等怎么办如果s1[i-1]和s2[j-1]不相等那两个字符不可能同时保留。可能的做法只有两种第一种删除s1[i-1]。删除后问题变成“让s1的前i-1个字符和s2的前j个字符变得相等”代价是dp[i-1][j]加上s1[i-1]的ASCII值。第二种删除s2[j-1]。同理问题变成“让s1的前i个字符和s2的前j-1个字符变得相等”代价是dp[i][j-1]加上s2[j-1]的ASCII值。取这两种方案中更小的一个就是dp[i][j]的最优值dp[i][j] min( dp[i-1][j] ord(s1[i-1]), dp[i][j-1] ord(s2[j-1]) )这里需要特别注意这里不是“只删除一个就行”的意思而是说当前这一步我们只决策这两个字符的去留后续子问题继续递归决策其他字符。比如s1 seas2 eatdp[3][3]的转移中s1最后一个字符是as2最后一个字符是t不相等。如果删掉a代价是dp[2][3] 97如果删掉t代价是dp[3][2] 116。算出来删t更便宜于是dp[3][3] 231。3.4 边界条件与遍历顺序边界条件其实就是“有一方变成空字符串”的情况。dp[0][0] 0两个都是空串已经相等不需要删任何字符。dp[i][0]s2为空想让s1的前i个字符变成空串只能把s1的这i个字符全部删掉。所以dp[i][0] dp[i-1][0] ord(s1[i-1])这是一个前缀和累积过程。dp[0][j]同理dp[0][j] dp[0][j-1] ord(s2[j-1])。遍历顺序上由于dp[i][j]依赖dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]三者只要保证外层从1到m遍历s1长度内层从1到n遍历s2长度全部依赖项都已经被计算出来遍历顺序没有任何问题。4. 代码实现与空间优化4.1 基础二维 DP 实现先用最直观的二维数组写一版把思路完整落地。Python代码如下class Solution: def minimumDeleteSum(self, s1: str, s2: str) - int: m, n len(s1), len(s2) dp [[0] * (n 1) for _ in range(m 1)] # 边界s2 为空s1 全部删除 for i in range(1, m 1): dp[i][0] dp[i - 1][0] ord(s1[i - 1]) # 边界s1 为空s2 全部删除 for j in range(1, n 1): dp[0][j] dp[0][j - 1] ord(s2[j - 1]) # 递推填表 for i in range(1, m 1): for j in range(1, n 1): if s1[i - 1] s2[j - 1]: dp[i][j] dp[i - 1][j - 1] else: dp[i][j] min( dp[i - 1][j] ord(s1[i - 1]), dp[i][j - 1] ord(s2[j - 1]) ) return dp[m][n]对应Java版本class Solution { public int minimumDeleteSum(String s1, String s2) { int m s1.length(), n s2.length(); int[][] dp new int[m 1][n 1]; for (int i 1; i m; i) { dp[i][0] dp[i - 1][0] s1.charAt(i - 1); } for (int j 1; j n; j) { dp[0][j] dp[0][j - 1] s2.charAt(j - 1); } for (int i 1; i m; i) { for (int j 1; j n; j) { if (s1.charAt(i - 1) s2.charAt(j - 1)) { dp[i][j] dp[i - 1][j - 1]; } else { dp[i][j] Math.min( dp[i - 1][j] s1.charAt(i - 1), dp[i][j - 1] s2.charAt(j - 1) ); } } } return dp[m][n]; } }Java里char参与算术运算会自动提升为int所以s1.charAt(i - 1)可以直接拿来加。这个版本的时间复杂度是O(mn)空间复杂度也是O(mn)。m和n最多1000二维数组1百万个int内存大概4MB完全没问题。但既然能优化我们还是聊一下滚动数组。4.2 滚动数组优化观察递推式可以发现dp[i][j]只依赖当前行的前一个元素dp[i][j-1]以及上一行的dp[i-1][j]、dp[i-1][j-1]。这意味着我们不需要保存完整的二维表只需要保留两行。class Solution: def minimumDeleteSum(self, s1: str, s2: str) - int: m, n len(s1), len(s2) dp [[0] * (n 1) for _ in range(2)] # 初始化第0行s1 为空s2 全部删除 for j in range(1, n 1): dp[0][j] dp[0][j - 1] ord(s2[j - 1]) for i in range(1, m 1): cur i 1 prev 1 - cur # 更新当前行第0列 dp[cur][0] dp[prev][0] ord(s1[i - 1]) for j in range(1, n 1): if s1[i - 1] s2[j - 1]: dp[cur][j] dp[prev][j - 1] else: dp[cur][j] min( dp[prev][j] ord(s1[i - 1]), dp[cur][j - 1] ord(s2[j - 1]) ) return dp[m 1][n]这里用i 1代替i % 2性能上略微快一点点主要是习惯问题。滚动数组的空间复杂度降到O(n)对于长字符串的极限场景会更从容。4.3 一维数组版本两行滚动数组其实还可以更进一步压成一行。一维数组写法的关键在于保存“左上角”那个值因为它在更新过程中会被覆盖。具体实现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[0] dp[0] ord(s1[i - 1]) # 当前行的 dp[0] for j in range(1, n 1): temp dp[j] # 保存旧行的 dp[j] if s1[i - 1] s2[j - 1]: dp[j] prev # 旧行的 dp[j-1]也就是左上角 else: dp[j] min( dp[j] ord(s1[i - 1]), dp[j - 1] ord(s2[j - 1]) ) prev temp return dp[n]这段代码容易把人绕晕我建议对照二维表格理解在处理第i行时dp数组心里装的还是第i-1行的值。dp[j]在被覆盖前代表的是dp[i-1][j]prev在进入第j列前代表的是dp[i-1][j-1]。所以在dp[j] prev这一步里我们其实是在读取还没被覆盖的左上角。一维版本空间最优但可读性差一些。如果你是在面试或者写题解我更推荐两行滚动数组的版本清晰程度高又不会丢分。5. 常见错误与调试记录5.1 初始化漏了前缀和有朋友一开始只初始化了dp[0][0] 0然后就直接从i1,j1开始填。这样会导致dp[1][1]在做min运算时把dp[0][1]或dp[1][0]当成0来算结果严重偏小。边界条件的本质是一方为空串时另一方必须全部删除。这个“全部删除”是一个累积代价不是某个单一字符的ASCII所以必须用一个循环从前一个状态递推出来。写成dp[i][0] dp[i-1][0] ord(s1[i-1])语义上就是在说要让i个字符变成空串先把前i-1个字符删光再删掉第i个。5.2 字符相等时误加 ASCII这是712这道题最有迷惑性的错误。可能有朋友觉得“保留了这个字符所以这个字符有保留价值应该加到dp里”。但dp统计的是“删除代价”你既然保留了它就不需要为它付费这里应该是dp[i][j] dp[i-1][j-1]而不是dp[i][j] dp[i-1][j-1] ord(s1[i-1])。如果误加了拿sea和eat来测结果会变成346而不是231一下子就能发现不对。之所以很多人会犯这个错是因为做LCS时“匹配字符”会贡献长度1到了加权版本里容易惯性思维觉得“也应该贡献一个ASCII值”。这里要时刻提醒自己dp的含义是删除代价不是保留收益。5.3 一维数组里 prev 被覆盖一维数组版本之所以容易写错问题就出在prev的更新时机。一个常见错误是先更新dp[j]再用被覆盖后的值去当左上角结果递推彻底乱掉。正确顺序是先保存dp[j]到temp再计算新的dp[j]最后把temp交给prev进入下一个j循环。这样在第j1列时prev就是旧行的第j个值即当前单元格的左上角。写一维版本时我建议在草稿纸上画出两行表格标出哪一个是旧值、哪一个是新值就这么一个小习惯能省下大量调bug的时间。5.4 与分析公式交叉验证写完代码以后可以用LCS公式做交叉验证。也就是说对任意测试用例先写出解法一的代码算出答案再跑解法二两边结果应该完全一致。如果对不上那就说明其中一边逻辑有问题通常问题都在边界初始化或者累加方向。我自己调试时常做的验证步骤是写一个打印二维dp表的辅助函数对sea和eat做一遍手算。手算的表长这样行表示s1的前缀列表示s2的前缀eat0101198314s115216313429e216115212328a313212115231走一遍这个表你对“为什么相等时取左上角”会有更具体的体感。比如dp[2][2]对应se和ea值是212意思是删掉s115和e97得到e和a不对让我重新想。dp[2][2]212对应的是让se和ea相等的最小代价。方案是删掉s1的s115和s2的e101那还剩e和a还是不等不对那需要继续删。看表格值212合理方案其实是删掉s1的s115然后保留e再删掉s2的e101那s2剩a还是不等。啊这里要从转移过程看dp[2][2]min(dp[1][2]ord(e), dp[2][1]ord(a)) min(313101414, 11597212) 212即删除s2的a97后让se和e相等后者又删掉s1的s115总代价212最后两边都剩e。这样理解就通了。表格打印出来配合转移路径看每一步都清清楚楚。6. 这道题延伸出的几条经验6.1 递推式和编辑距离是一家人看懂712的递推式之后再回看72题编辑距离、583题两个字符串的删除操作、1143题最长公共子序列会发现它们的骨架几乎一模一样差别只在“代价函数”上。1143问最长公共子序列长度对应的是“匹配得1分”583问最少删除次数对应的是“删除得1分”712问最小ASCII删除和对应的是“删除时加权权重为ASCII码”。这套“看最后一个字符 分情况讨论删除谁”的套路几乎能覆盖所有同类字符串DP题。把712彻底吃透比单纯多刷三道题更划算。6.2 状态定义里藏着答案我刷题时有个体会动态规划题最怕的不是转移方程难推而是状态定义没说清。712这道题的好处在于状态定义可以直接从题目描述里翻译过来——“最小ASCII删除和”本身就是dp[i][j]的语义。当你发现一道题套不上任何模板时试着把题目的核心名词原封不动地写进状态定义里往往思路就开了。6.3 写完代码后给自己留一组自测用例我提交前固定会跑这几组用例s1s2期望输出说明seaeat231题目示例经典场景deleteleet403题目示例验证非连续LCSab195无公共字符全删aa0完全相同一个都不用删aaaaaa0重复字符验证相等分支abba194交叉场景验证min逻辑最后一组ab和ba值得说一下。公共子序列只能挑一个字符保留a就得删s1的b(98)和s2的b(98)代价196保留b删两个a(9797)代价194所以答案是194。这种边界用例能帮你确认转移方程里的min是不是真的在正常工作。6.4 空间优化值得做但不值得牺牲可读性有时候在简洁和效率之间要做一个平衡。712在LeetCode上m和n最多1000二维dp数组4MB以内OJ上完全跑得动。我自己的建议是如果是在做题阶段先用二维版本把思路跑通再用滚动数组优化如果是在面试现场写二维版本足够面试官更在意你的思路是否清晰而不是那几MB内存。我实际刷题时会把一维版本题解收藏起来在写其他字符串DP时参考。但遇到新题还是先老老实实写二维版本验证逻辑等AC之后再回头做空间优化。这样心理负担小出错率也低回头再看一维数组版本时由于已经理解整个递推表优化代码也不容易写错。712这道题如果只做一遍就过很难体会到它和583、72之间的联系。建议刷完之后顺着“删除操作”这条线把相关题目放在一起对比着看你会发现最小ASCII删除和只是把删除次数换成了删除权重递推骨架上没有任何变化。这大概就是刷题刷到后面最舒服的感觉——见过的套路越多新题就越像老朋友。