1. 题目拆解：什么是最小ASCII删除和
1.1 先理解题目的本质
LeetCode 712这道题，给定两个字符串s1和s2，要求我们通过删除字符的方式，使得两个字符串变得完全相同。但删除字符是有代价的，每个字符的代价就是它的ASCII码值。最后要算出：在保证删除后两个字符串相等的前提下，删除的字符ASCII值总和最小是多少。
这个题别看表面是“删除”，很多人第一反应是去模拟删除的过程——先看看哪些字符相同，哪些不同，然后把不同的删掉。我当初也是这么想的，结果走入了误区。举个例子，s1 = "sea"，s2 = "eat"，如果只删不同的字符，需要删掉s1中的s（ASCII 115），再删掉s2中的t（ASCII 116），删除总值231。但更好的方案是：保留ea，删掉s和t，同时s1里的e和s2里的e对应，a和a对应，删除的也是这两个字符，总值一样是231。看起来似乎没有更优解了。但如果换个例子，比如s1 = "delete"，s2 = "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) # 一维滚动数组，长度取n+1，也可以取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初始化是干嘛的？当j=1时，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，这样下一次循环（j+1）的时候，prev里面存的就是f[i-1][j]，恰好就是f[i-1][(j+1)-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')是97，ord('A')是65。大写字母的ASCII比小写字母低32。这个题给的是任意可见ASCII字符，所以不需要特殊处理大小写。但有一点要注意：题目说ASCII删除和，所以计算的是十进制的ASCII值，不是Unicode码点，也不是字符个数。这和你平时做的普通LCS不同——普通LCS每个字符权重是1，这题每个字符权重是它自己的ASCII值。权重不同，直接导致同样的字符串组合，答案可能大相径庭。
4.4 实战中我用来验证的小技巧
写完代码后，我一般不会只跑题目给的示例，而是自己构造几组特殊用例来验证：
- 两个完全相同的字符串：比如
s1 = "abc"，s2 = "abc"，结果应该是0。 - 其中一个为空串：比如
s1 = ""，s2 = "abc"，结果应该是ord('a') + ord('b') + ord('c') = 294。 - 两个字符串没有公共字符：比如
s1 = "abc"，s2 = "xyz"，结果应该是两个字符串所有字符ASCII和，也就是294 + (120+121+122) = 657。 - 有重复字符的情况：比如
s1 = "aaa"，s2 = "aa"，结果应该是删除一个'a'，即97。
这几个用例能快速捕捉到初始化错误和递推关系错误。在LeetCode的编辑页里，这些用例可以放在"测试用例"框中进行本地验证。实际上这题的通过率并不高，很多人第一次提交就是挂在空串或者是边界下标等细节上。
4.5 时间复杂度和空间复杂度实测
从复杂度分析来看：
- 时间复杂度：双重循环遍历m×n，因此是O(m×n)。字符串长度最多1000时，100万次操作在Python里完全不是问题。
- 空间复杂度：一维数组长度为n+1，因此是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 = "sea"，s2 = "eat"。公共子序列中ASCII和最大的是"ea"，e = 101，a = 97，和为198。总ASCII和：s1 = 115 + 101 + 97 = 313，s2 = 101 + 97 + 116 = 314，总和627。最小删除和 = 627 - 2×198 = 231。正确。
示例2的详细计算过程：
s1 = "delete"的ASCII值：100+101+108+101+116+101=627；s2 = "leet"的ASCII值：108+101+101+116=426，总和1053。最优公共子序列是"let"，ASCII和为108+101+116=325（也可以选"lee"，和也是108+101+101=310，不如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)这样n+1就是min(len(s1), len(s2)) + 1，空间最小化才是正确的。这个细节很容易写反，我特意在这里停一下复盘，就是想强调：做空间优化时，要把较短的维度放在滚动轴上。如果放反了，虽然代码也能跑，但空间优化就没达到预期效果。
这个错误我在面试模拟时犯过一次，当时被面试官追问了一句"你这么交换，空间真的变少了吗"，我立刻意识到自己把内外层搞反了。所以我现在写这个优化都会多加一个注释提醒自己。你在自己实现时，建议在交换后打印一下len(s1)和len(s2)，一眼就能看出谁长谁短，避免这种低级失误。
在我个人的刷题经验里，这道题值得做的原因在于：它不只是一个孤立题目，而是连接LCS、编辑距离、滚动数组优化这三个知识点的枢纽。如果把普通LCS比作"数个数"的入门题，这道题就是"算权重"的进阶题，而状态压缩则是从"会做"到"做得漂亮"的关键一步。把这些串起来理解，比单刷十道题都管用。
