企业官网建设流程全解析

面试被这道题卡住？5分钟带你搞懂「最小ASCII删除和」

“给定两个字符串，删掉一些字符让它们相等，但删掉的每个字符都要’收费’——按 ASCII 值收费。怎么删最省钱？”

这不是什么奇怪的计价规则，而是 LeetCode 第 712 题——两个字符串的最小 ASCII 删除和。

它和大名鼎鼎的编辑距离是亲兄弟，但面试命中率却不相上下。搞懂了这道题，你对二维 DP 的理解就真正毕业了。

先举个栗子：到底在问什么？

输入：s1 = "sea", s2 = "eat" 输出：231

解释：

• 从"sea"中删掉's'（ASCII 值 115），变成"ea"
• 从"eat"中删掉't'（ASCII 值 116），变成"ea"
• 两个字符串相等了！花费：115 + 116 =231

注意：你不能插入或替换，只能删除。而且删哪个字符是有代价的——按它的 ASCII 值收费。

核心直觉：这道题和编辑距离有什么区别？

如果你做过编辑距离（LeetCode 72），你可能会有既视感：

所以本质上，这是编辑距离的简化版 + 加权版：

• 简化：不用考虑"插入"和"替换"
• 加权：删除代价从固定的 1 变成了字符的 ASCII 值

五步法推导：从零到完整代码

第一步：定义状态

dp[i][j]= 使s1的前i个字符 和s2的前j个字符 相等，所需要删除的字符的 ASCII 值的最小和

进一步理解：dp[i][j]= 从s1的前i个字符中删一些，从s2的前j个字符中删一些，使得剩下的字符串相同**，所需删除字符的 ASCII 值的最小和**

这里的i和j是长度（前几个字符），不是下标。

第二步：状态转移方程

假设现在处理dp[i][j]，两字符串的最后一个字符分别是s1[i-1]和s2[j-1]。

✅ 情况一：两个字符相等

s1[i-1] == s2[j-1]

太好了！这个字符不用删，问题缩小一格：

dp[i][j] = dp[i-1][j-1]

✅ 情况二：两个字符不相等

只能删除，有两种选择：

取最小值：

dp[i][j] = min(dp[i-1][j] + s1[i-1], dp[i][j-1] + s2[j-1])

第三步：初始化边界

画个表格就懂了（以s1="sea",s2="eat"为例）：

• dp[0][0] = 0：空串转空串，不需要删
• dp[i][0]：s1 前 i 个字符变成空串，只能全部删掉

  dp[i][0] = dp[i-1][0] + s1[i-1]

• dp[0][j]：空串变成…（即 s2 前 j 个字符全部删掉）

  dp[0][j] = dp[0][j-1] + s2[j-1]

第四步：遍历顺序

dp[i][j]依赖三个方向：

↖ dp[i-1][j-1] ↑ dp[i-1][j] ← dp[i][j-1] ? dp[i][j]

必须从左到右、从上到下遍历。

for(inti=1;i<=m;i++){for(intj=1;j<=n;j++){// 计算 dp[i][j]}}

第五步：验证填表

手动填一遍s1="sea",s2="eat"的表格：

几个关键推导：

• dp[2][1]：s1[1]='e',s2[0]='e'相等→dp[1][0] = 115
• dp[3][2]：s1[2]='a',s2[1]='a'相等→dp[2][1] = 115
• dp[3][3]：s1[2]='a',s2[2]='t'不相等
  • 删a：dp[2][3] + 97 = 328 + 97 = 425
  • 删t：dp[3][2] + 116 = 115 + 116 = 231
  • 取最小：231✅

答案正确！

完整代码（Java）

classSolution{publicintminimumDeleteSum(Strings1,Strings2){intm=s1.length(),n=s2.length();int[][]dp=newint[m+1][n+1];// 初始化第一列：s1 前 i 个字符全部删除for(inti=1;i<=m;i++){dp[i][0]=dp[i-1][0]+s1.charAt(i-1);}// 初始化第一行：s2 前 j 个字符全部删除for(intj=1;j<=n;j++){dp[0][j]=dp[0][j-1]+s2.charAt(j-1);}// 填表for(inti=1;i<=m;i++){for(intj=1;j<=n;j++){if(s1.charAt(i-1)==s2.charAt(j-1)){// 字符相等，不用删dp[i][j]=dp[i-1][j-1];}else{// 二选一：删 s1 的字符，或删 s2 的字符dp[i][j]=Math.min(dp[i-1][j]+s1.charAt(i-1),// 删除 s1[i-1]dp[i][j-1]+s2.charAt(j-1)// 删除 s2[j-1]);}}}returndp[m][n];}}

时间复杂度：O(m * n)
空间复杂度：O(m * n)（可优化到 O(min(m,n))）

一句话总结

这道题就是编辑距离的"删减版"——把三种操作缩成一种删除操作，把固定代价 1 换成字符 ASCII 值。

只要记住这个公式：

相等：dp[i][j] = dp[i-1][j-1] 不等：dp[i][j] = min(删s1, 删s2)

二维字符串 DP 的核心套路你就掌握了。下一道最长公共子序列，也是同样的配方。

觉得有用？收藏起来，面试前翻一翻，DP 稳如老狗。

欢迎在评论区交流你的 DP 学习心得，或者留下你想了解的算法题，下期安排！