最近把 LeetCode 的动态规划专题又翻出来刷了一遍712 这道“两个字符串的最小 ASCII 删除和”是绕不过去的一道题。第一眼看到题目会觉得它和经典的“最长公共子序列”很像但真上手之后才发现把删除成本从“字符个数”换成“字符 ASCII 值总和”之后状态设计、边界处理、甚至代码排错的方式都会跟着变。这篇文章想完整拆解这道每日一题的解法二——递推也就是自底向上的表格法包括状态定义、转移方程怎么推、代码怎么从记忆化搜索改写成递推以及我自己在调试过程中踩过的几个隐蔽的坑。1. 题目到底在问什么为什么最小 ASCII 删除和不是“最小删除字符数”1.1 题面回顾与两个样例的直观拆解题目给两个字符串 s1 和 s2要求返回“使两个字符串相等所需删除字符的 ASCII 值的最小和”。注意这里的代价不是删除的字符个数而是每个被删字符的 ASCII 码值之和。第一个样例是 s1 seas2 eat。sea 的字符 ASCIIs 115e 101a 97。eat 的字符 ASCIIe 101a 97t 116。如果只考虑“删多少个字符”最简单的方式是把 s1 的 s 删掉把 s2 的 t 删掉两个字符串都变成 ea一共删除 2 个字符。对应 ASCII 和是 115 116 231。这个方案恰好也是最小的所以输出 231。第二个样例是 s1 deletes2 leet。最终可以让两个字符串都变成 lets1 删掉 d(100)、e(101)、e(101)代价 302。s2 删掉 e代价 101。总和 403。这里有个细节值得注意直接删掉 s1 中三个字符、删掉 s2 中一个字符一共删了 4 个字符数量上并不是最少的。但这道题问的是 ASCII 和最小而不是删得最少所以数量次优的方案反而可能是代价最优的。1.2 和“583. 两个字符串的删除操作”放在一起看才明白坑在哪LeetCode 上有一道 583 题所求的是“使两个字符串相等所需删除字符数的最小值”。两道题几乎一模一样唯一的区别就是 583 的每个字符删除成本是 1而 712 的每个字符删除成本是它的 ASCII 码值。这个区别看起来只是“1 换成 ord(c)”但影响非常大项目583 两个字符串的删除操作712 两个字符串的最小ASCII删除和单个字符删除成本恒为 1ord(c)字符越大越“贵”状态定义dp[i][j] 表示最少删除个数dp[i][j] 表示最小 ASCII 删除和边界初始化dp[i][0] idp[i][0] 前 i 个字符 ASCII 和转移代价1ord(字符)把两道题放在一起刷才能意识到“代价函数”的变化会牵动整个 DP 的写法。很多同学把 583 的代码改一改交上去结果边界初始化那一步还是写的dp[i][0] i这就是第一道坎。它和最长公共子序列LCS的关系也值得说一句LCS 求的是“保留哪些字符能得到最长公共序列”而 712 求的是“删掉哪些字符能让剩余部分相等且 ASCII 和最小”。LCS 是“最大化保留的价值”712 是“最小化删除的成本”两者天然是对偶的。如果用 LCS 的思路硬套会纠结于“公共子序列”的长度而在这里我们其实并不关心公共部分是什么只关心删掉了什么。2. 递推前的关键一步先把 dp 状态定义清楚边界才会顺2.1 dp[i][j] 的语义处理的是“前缀”不是“区间”写递推第一步永远是状态定义。712 的状态定义和其他双串 DP 一样用二维数组dp[i][j] 表示s1 的前 i 个字符即 s1[0..i-1]和 s2 的前 j 个字符即 s2[0..j-1]使这两个前缀相等所需的最小 ASCII 删除和。这里必须强调索引偏移。字符串下标习惯从 0 开始但 DP 数组的索引从 0 到 len(s) 一共有 len(s)1 个位置其中 dp[i] 对应的是前缀长度 i而不是“以下标 i 结尾”的某个子串。为什么要这样定义因为只有引入“前缀长度 0”这个概念才能自然表达空串的情况dp[0][0] 表示两个空串它们已经相等不需要删除任何字符值是 0。dp[i][0] 表示 s1 的前 i 个字符和空串相等那只能把 s1 前 i 个字符全部删掉。dp[0][j] 同理表示把 s2 前 j 个字符全部删掉。如果定义成“s1[0..i] 和 s2[0..j]”这种闭区间形式边界就得单独处理 i -1 或者 j -1 的情况实现起来非常别扭。前缀长度定义是双串 DP 的通用惯例后面写的所有转移都建立在这个定义上。2.2 边界的 ASCII 累加怎么写才不会掉进 583 的惯性里边界初始化需要把“全部删除”的代价算出来。因为删除成本是 ASCII 值所以不能直接写循环下标而要做前缀累加。# 错误惯性写法把删除成本当成字符个数 for i in range(1, m 1): dp[i][0] i # 这是 583 的写法712 里是错的 # 正确写法累加 ASCII 值 for i in range(1, m 1): dp[i][0] dp[i - 1][0] ord(s1[i - 1]) for j in range(1, n 1): dp[0][j] dp[0][j - 1] ord(s2[j - 1])s1[i - 1]是当前要删掉的字符dp[i - 1][0]是删掉前 i-1 个字符的总代价两者相加就是从 i 个字符删到空串的总代价。这里用“累加”而不是“查前缀和数组”是因为在填写整个 dp 表的过程中边界行本来就要逐格推进顺手累加最省事。初始化完成之后dp 表的第一行和第一列就已经被确定了。后面所有的递推填的都是内部格子每个内部格子都依赖左上、上、左三个方向的值。3. 状态转移方程的推演盯住两个字符串的“尾巴”3.1 末尾字符相等直接继承不要犹豫假设现在要计算 dp[i][j]也就是让 s1[0..i-1] 和 s2[0..j-1] 相等。先看两个字符串的最后一个字符如果 s1[i - 1] s2[j - 1]说明这两个字符已经对齐了它们不需要被删除。这时候只需要让前面的部分相等即可dp[i][j] dp[i - 1][j - 1]有同学会问为什么不能把这两个相等的字符也删掉然后取一个更小的值答案是每个字符的删除成本都是正数删掉它们只会让代价变大。换句话说如果某个最优方案里删掉了这两个相等的字符我可以把其中一个“恢复”出来把它拼在最终得到的公共字符串末尾删除代价立即减少而且两个字符串依然相等。所以最优方案里一定存在一种做法是保留这两个相等字符的直接取 dp[i - 1][j - 1] 就是安全的。这一点和 LCS 的转移逻辑很像差别只在 LCS 遇到相等字符时是“长度加一”这里是不额外付出代价直接继承。3.2 末尾字符不等必须删一个比较“删谁更便宜”如果 s1[i - 1] ! s2[j - 1]这两个字符没有办法同时保留在公共结果里至少要删掉其中一个。于是有两种方向删掉 s1 的末尾字符代价是 ord(s1[i - 1])然后让 s1[0..i-2] 和 s2[0..j-1] 去相等也就是 dp[i - 1][j]。删掉 s2 的末尾字符代价是 ord(s2[j - 1])然后让 s1[0..i-1] 和 s2[0..j-2] 去相等也就是 dp[i][j - 1]。两者取最小值dp[i][j] min( ord(s1[i - 1]) dp[i - 1][j], ord(s2[j - 1]) dp[i][j - 1] )这个“删 A 还是删 B”的决策本质上是在回答一句话谁被删掉之后剩下的子问题更便宜。真实计算时两个候选都会算一遍min 会帮我们选出更划算的一边。有人会想能不能把 s1 和 s2 的末尾字符都删掉然后让前面的部分相等这个方案理论上存在但它等价于“先删掉 s1 的末尾字符进入 dp[i-1][j]”然后在 dp[i-1][j] 的子问题里再删掉 s2 的某个字符。这个方案一定被 min 覆盖到了并不会漏掉最优解所以在转移方程里不需要单独写一个ord(s1[i-1]) ord(s2[j-1]) dp[i-1][j-1]的分支。3.3 手推一遍“sea”和“eat”的 DP 表把方程坐实纸上推一遍比看十遍代码都管用。我用 s1 seas2 eat 来完整填表。首先生成边界。第一行是 s2 前缀的 ASCII 累加dp[0][1]101dp[0][2]10197198dp[0][3]198116314。第一列是 s1 前缀的 ASCII 累加dp[1][0]115dp[2][0]115101216dp[3][0]21697313。然后一行一行填内部dp[1][1]s[0]se[0]e不等。min(115dp[0][1]216, 101dp[1][0]216)216。dp[1][2]s vs a不等。min(115198313, 97216313)313。dp[1][3]s vs t不等。min(115314429, 116313429)429。dp[2][1]e vs e相等。dp[2][1]dp[1][0]115。dp[2][2]e vs a不等。min(101313414, 97115212)212。dp[2][3]e vs t不等。min(101429530, 116212328)328。dp[3][1]a vs e不等。min(97115212, 101313414)212。dp[3][2]a vs a相等。dp[3][2]dp[2][1]115。dp[3][3]a vs t不等。min(97328425, 116115231)231。完整表格如下dpj0j1 (e)j2 (a)j3 (t)i00101198314i1 (s)115216313429i2 (e)216115212328i3 (a)313212115231右下角 231 就是答案。我建议所有刷 DP 题的人都要养成“手工填表”的习惯。表格填完一遍你对转移方向的理解就不是背公式而是真正知道每个格子是从哪三个方向推过来的。特别是 dp[3][2] 这个格子填它的时候用的是“相等继承”直接从左上角 115 抄过来这一步会让人突然意识到“末尾字符相等时前面已经付出的删除代价一个都不用增加”。4. 递推代码落地从记忆化搜索到自底向上的改写逻辑4.1 解法一回顾自顶向下递归的样子标题说了解法二是递推但如果不回顾一下解法一就很难理解为什么递推的代码长这样。解法一是自顶向下的记忆化搜索思路非常直观from functools import lru_cache def minimumDeleteSum(s1: str, s2: str) - int: lru_cache(None) def dfs(i: int, j: int) - int: if i len(s1): return sum(ord(c) for c in s2[j:]) if j len(s2): return sum(ord(c) for c in s1[i:]) if s1[i] s2[j]: return dfs(i 1, j 1) return min( ord(s1[i]) dfs(i 1, j), ord(s2[j]) dfs(i, j 1) ) return dfs(0, 0)这段代码的递归出口和递推的边界初始化是一一对应的i len(s1)对应 dp[len(s1)][j] 那一列含义是 s1 已删空剩下的 s2[j:] 全部删掉。j len(s2)对应 dp[i][len(s2)] 那一行。s1[i] s2[j]对应递推里的“相等继承”。最后一个 min 对应“删 A 还是删 B”。递归版的好处是思维负担小坏处是每次状态转移都要压栈lru_cache本身也有哈希开销对比较长的字符串会明显慢一截。递推版把这些状态转移变成两层 for 循环里的一次次查表和填表是更标准的工程写法。4.2 从递归到递推的三步改写法从上面的 dfs 改写递推版只需要三个动作参数 i、j 变成 dp 数组下标。递归出口变成边界初始化。递归调用变成查 dp 表。于是得到最朴素的二维递推代码def minimumDeleteSum(s1: str, s2: str) - int: m, n len(s1), len(s2) dp [[0] * (n 1) for _ in range(m 1)] for i in range(1, m 1): dp[i][0] dp[i - 1][0] ord(s1[i - 1]) 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]为什么循环里的 i 和 j 都要从 1 开始因为第 0 行和第 0 列已经在初始化时填完了内部格子依赖的是“上一行”和“左一格”从 1 开始才能保证每次取到的 dp[i-1]、dp[j-1] 都是已经被填好的值。遍历方向是 i 从小到大、j 从小到大这是由依赖关系决定的dp[i][j] 依赖的 dp[i-1][j] 在上一行dp[i][j-1] 在左边dp[i-1][j-1] 在左上角只有按这个顺序遍历三个依赖值才是现成的。4.3 滚动数组优化先写双数组版再挑战单数组版二维 dp 的空间复杂度是 O(m*n)。712 的字符串长度不超过 1000二维数组其实完全够用但面试或者做题时习惯性优化一把还是值得的。观察转移方程可以发现每个 dp[i][j] 只依赖当前行的左边一格和上一行的两个格子并不依赖更早的行。所以可以用滚动数组把空间压到 O(n)。最容易理解的是双数组滚动也就是用 pre 保存上一行用 cur 填当前行def minimumDeleteSum(s1: str, s2: str) - int: m, n len(s1), len(s2) pre [0] * (n 1) for j in range(1, n 1): pre[j] pre[j - 1] ord(s2[j - 1]) for i in range(1, m 1): cur [0] * (n 1) cur[0] pre[0] ord(s1[i - 1]) for j in range(1, n 1): if s1[i - 1] s2[j - 1]: cur[j] pre[j - 1] else: cur[j] min( pre[j] ord(s1[i - 1]), cur[j - 1] ord(s2[j - 1]) ) pre cur return pre[n]这个版本里pre[j]就是上一行的 dp[i-1][j]pre[j-1]就是左上角的 dp[i-1][j-1]cur[j-1]是已经填好的当前行左边一格。逻辑和二维版一一对应几乎不会写错。如果还想再省一半空间可以只保留一个数组维护一个 prev 变量来记录左上角def minimumDeleteSum(s1: str, s2: str) - int: m, n len(s1), len(s2) dp [0] * (n 1) 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] ord(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]单数组版的精髓在 prev 变量它保存的是“还没被当前行覆盖的上一行左边一格”。每次更新 dp[j] 之前先用 temp 把旧值暂存起来这样下一轮 j1 需要用左上角 dp[i-1][j] 时temp 就变成了 prev。这里最容易出错的地方是更新顺序我会在下一章专门展开讲。5. 调试递推时最容易踩的隐藏坑以及怎么验证自己没写错5.1 坑一边界初始化沿用了 583 的习惯把成本当成了数量这是我见过最多人踩的坑。如果同时刷过 583 和 712很容易把 583 的边界写法直接搬过来dp[i][0] i但 712 里删除一个字符的成本是它的 ASCII 值不是 1。用i做边界的结果是当 s1 前缀很长、ASCII 值很大时所有依赖边界的格子都会低估删除成本最后算出来的答案大概率偏小。验证方法很简单拿题目第二个样例跑一遍。s1 deletes2 leet正确答案是 403。如果边界写错答案会明显偏离。更通用的小技巧是自己在代码里打印一条最长边界的值dp[10][0] 的正确值应该是 s1 前 10 个字符的 ASCII 累加而错误写法是 10一眼就能看出来。5.2 坑二滚动数组的更新顺序反了把“上一行旧值”用成了“当前行新值”很多同学是先从背包问题接触滚动数组的背包问题里常常要求内层循环从大到小遍历以复用上一维的数据。到了双串 DP这个惯性非常容易误导人。在单数组滚动版里内层循环的 j 必须从小到大。原因在于更新 dp[j] 时等号右侧的 dp[j-1] 需要的不是上一行的旧值而是本轮已经填好的当前行左边一格。如果从大到小遍历dp[j-1] 还是上一行的旧值整个递推就变成了在错误的方向上使用数据结果会完全错乱。反过来比较一下背包问题的“从大到小”是为了防止一件物品被重复放入双串 DP 的“从小到大”是为了让当前行左边的新值可以被后续格子使用。两类问题滚动数组的遍历方向恰恰相反刷题多的人特别容易混淆。我自己的习惯是写滚动数组之前先口头说一遍每个依赖值是“上一行的”还是“当前行的”说清楚了再动笔。5.3 坑三写完递推不放心用记忆化搜索对拍最快递推代码写完之后最有效的验证方式不是盯着代码看而是写一个暴力解或者直接保留记忆化搜索版本对拍随机小数据。我自己常用的做法是写一个暴力递归不带记忆化也行数据小就扛得住。随机生成若干组长度在 1 到 8 之间的字符串字符集用 a-z。把暴力结果和递推结果逐个比较不一致就打印当前用例。对拍脚本不需要很长核心逻辑就是import random import string def brute(s1: str, s2: str) - int: # 暴力枚举所有删除组合取最小 ASCII 和 ... for _ in range(1000): s1 .join(random.choices(string.ascii_lowercase, krandom.randint(1, 8))) s2 .join(random.choices(string.ascii_lowercase, krandom.randint(1, 8))) if minimumDeleteSum(s1, s2) ! brute(s1, s2): print(s1, s2) break对拍跑过 1000 组随机数据递推状态转移的正确性基本就坐实了。这种方法比肉眼检查可靠得多尤其是在边界初始化和滚动数组这种容易出细节问题的地方。5.4 把递推模板延伸出去一类双串 DP 的通用写法712 的递推写法一旦吃透对同类型的题目会形成很强的迁移能力。我简单总结一个通用套路状态一律定义成“前 i 个字符”和“前 j 个字符”的前缀形式。边界先处理空串想清楚“空串和另一串相等”的代价是什么。转移时永远盯着 s1[i-1] 和 s2[j-1] 这一对末尾字符相等就继承左上不等就讨论“删谁更便宜”。遍历顺序按依赖方向来不要背任何口诀。这个套路可以直接套到 LCS、583、编辑距离等一大批双串 DP 上。区别只在于“代价函数”和“目标量”。比如 LCS 的目标是最大保留长度遇到相等字符是 dp[i-1][j-1]1不等时是 max(dp[i-1][j], dp[i][j-1])编辑距离则多了一种“替换”操作转移分支会多一个。把 712 的转移方程理解了再看这些题会非常轻松。最后再说一个我个人的习惯每道 DP 题写完递推之后我都会把表格的最后一格倒着回溯一遍从 dp[m][n] 一路倒退到 dp[0][0]看看到底删了哪些字符。712 这道题回溯出来通常会得到一眼看不出来的删除方案但这个过程会让你对“dp[i][j] 究竟是哪些字符被留下了”有一种直觉。刷 DP 题最忌讳的是把状态转移方程当公式背亲手推一遍表格、回溯一遍路径才是真正把递推吃进脑子里。