面试被这道题卡住5分钟带你搞懂「最小ASCII删除和」“给定两个字符串删掉一些字符让它们相等但删掉的每个字符都要’收费’——按 ASCII 值收费。怎么删最省钱”这不是什么奇怪的计价规则而是 LeetCode 第 712 题——两个字符串的最小 ASCII 删除和。它和大名鼎鼎的编辑距离是亲兄弟但面试命中率却不相上下。搞懂了这道题你对二维 DP 的理解就真正毕业了。先举个栗子到底在问什么输入s1 sea, s2 eat 输出231解释从sea中删掉sASCII 值 115变成ea从eat中删掉tASCII 值 116变成ea两个字符串相等了花费115 116 231注意你不能插入或替换只能删除。而且删哪个字符是有代价的——按它的 ASCII 值收费。核心直觉这道题和编辑距离有什么区别如果你做过编辑距离LeetCode 72你可能会有既视感编辑距离最小 ASCII 删除和允许的操作增、删、改只能删每次操作的代价都是 1被删字符的ASCII 值DP 维度二维二维所以本质上这是编辑距离的简化版 加权版简化不用考虑插入和替换加权删除代价从固定的 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]✅ 情况二两个字符不相等只能删除有两种选择选择做了什么花费删除s1[i-1]s1 少了一个字符s2 目标不变dp[i-1][j] s1[i-1]删除s2[j-1]s2 少了一个字符s1 不变dp[i][j-1] s2[j-1]取最小值dp[i][j] min(dp[i-1][j] s1[i-1], dp[i][j-1] s2[j-1])第三步初始化边界画个表格就懂了以s1sea,s2eat为例“”eat“”0???s????e????a????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(inti1;im;i){for(intj1;jn;j){// 计算 dp[i][j]}}第五步验证填表手动填一遍s1sea,s2eat的表格“”e(101)a(97)t(116)“”0101198314s(115)115216313429e(101)216115212328a(97)313212115231几个关键推导dp[2][1]s1[1]e,s2[0]e相等→dp[1][0] 115dp[3][2]s1[2]a,s2[1]a相等→dp[2][1] 115dp[3][3]s1[2]a,s2[2]t不相等删adp[2][3] 97 328 97 425删tdp[3][2] 116 115 116 231取最小231✅答案正确完整代码JavaclassSolution{publicintminimumDeleteSum(Strings1,Strings2){intms1.length(),ns2.length();int[][]dpnewint[m1][n1];// 初始化第一列s1 前 i 个字符全部删除for(inti1;im;i){dp[i][0]dp[i-1][0]s1.charAt(i-1);}// 初始化第一行s2 前 j 个字符全部删除for(intj1;jn;j){dp[0][j]dp[0][j-1]s2.charAt(j-1);}// 填表for(inti1;im;i){for(intj1;jn;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 学习心得或者留下你想了解的算法题下期安排
