两个字符串的最小 ASCII 删除和 图解题解

删字符让两串相等，为什么代价按 ASCII 算

给两个字符串 s1、s2，只能删字符让它们变成完全一样，每删一个字符付出它的 ASCII 值（每个字符对应的数字编号，如 a=97）作代价，求最小总代价。关键是被删字符的 ASCII 之和最小、不是删的个数最少。

为什么不能先求最长公共子序列、其余全删

最直接是枚举「留哪些字符」：两串各留一个子序列（可不连续）使之相等、其余全删。可长 m、n 的串子序列有 2^m、2^n 种，指数爆炸跑不完。

留下的必是公共子序列，留最长的不就删得最少？但本题代价按 ASCII 加权：保留字符的 ASCII 权重和才决定省多少、不看个数，最长的未必最省。不如直接对删除代价做动态规划（DP，存子问题避免重算）。

dp[i][j] 存的是哪两段前缀的最小删代价

定义 dp[i][j] 为「让 s1 前 i 个字符和 s2 前 j 个字符相等的最小删除代价」，答案是 dp[m][n]。开 (m+1)×(n+1) 的表，第 0 行、第 0 列代表某串取空串：dp[0][0]=0；某串空时另一串只能全删，dp[i][0] 是 s1 前 i 个的 ASCII 前缀和，dp[0][j] 同理。

字符相同为什么抄左上角、不同为什么取两个方向的较小

算 dp[i][j] 看 s1 第 i 个字符 a、s2 第 j 个字符 b。相同时 a、b 都留、谁都不删，代价等于各砍掉这一字符后的子问题 dp[i-1][j-1]，直接抄左上角、不加 ASCII。

不同时至少删一个。删 a 是 ord(a)（取 a 的 ASCII 值）加 dp[i-1][j]，删 b 是 ord(b) 加 dp[i][j-1]，取较小：dp[i][j]=min(dp[i-1][j]+ord(a), dp[i][j-1]+ord(b))。相同却加 ASCII 会多算，只看一个方向会漏掉更省的删法。

拿 sea 和 eat 把这张表填出 231

ASCII：s=115、e=101、a=97、t=116。边界第 0 列 dp[1..3][0]=115、216、313，第 0 行 dp[0][1..3]=101、198、314。

s 对 e、a、t 都不同，首格显式算一次：dp[1][1]=min(dp[0][1]+115, dp[1][0]+101)=216，之后压缩写 dp[1][2]=313、dp[1][3]=429。第 2 个 e 对 e 相同，抄 dp[1][0]=115；e 对 a 取 min(414,212)=212，e 对 t 取 min(530,328)=328。第 3 个 a 对 e 得 212，a 对 a 相同抄 dp[2][1]=115，a 对 t 取 min(425,231)=231，右下角 dp[3][3]=231。

空串边界怎么铺，无公共字符时代价是多少

整张表 (m+1)(n+1) 格、每格 O(1) 转移，时间 O(m×n)；dp[i][j] 只依赖正上、正左、左上角，滚动数组只留一行把空间压到 O(n)。两个边界：某串为空则另一串全删，代价是它的 ASCII 总和；两串毫无公共字符则各自删空，答案是两串 ASCII 总和相加。

Python

class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        n = len(s2)
        dp = [0] * (n + 1)
        for j, ch in enumerate(s2, 1):
            dp[j] = dp[j-1] + ord(ch)
        for a in s1:
            prev = dp[0]
            dp[0] += ord(a)
            for j, b in enumerate(s2, 1):
                old = dp[j]
                if a == b:
                    dp[j] = prev
                else:
                    dp[j] = min(dp[j] + ord(a), dp[j-1] + ord(b))
                prev = old
        return dp[n]

C++

#include <algorithm>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int n = s2.size();
        vector<int> dp(n + 1);
        for (int j = 1; j <= n; ++j) dp[j] = dp[j-1] + s2[j-1];
        for (char a : s1) {
            int prev = dp[0];
            dp[0] += a;
            for (int j = 1; j <= n; ++j) {
                int old = dp[j];
                if (a == s2[j-1]) dp[j] = prev;
                else dp[j] = min(dp[j] + (int)a, dp[j-1] + (int)s2[j-1]);
                prev = old;
            }
        }
        return dp[n];
    }
};

Java

import java.util.*;
class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int n = s2.length();
        int[] dp = new int[n + 1];
        for (int j = 1; j <= n; j++) dp[j] = dp[j - 1] + s2.charAt(j - 1);
        for (char a : s1.toCharArray()) {
            int prev = dp[0];
            dp[0] += a;
            for (int j = 1; j <= n; j++) {
                int old = dp[j];
                if (a == s2.charAt(j - 1)) dp[j] = prev;
                else dp[j] = Math.min(dp[j] + a, dp[j - 1] + s2.charAt(j - 1));
                prev = old;
            }
        }
        return dp[n];
    }
}