712. 两个字符串的最小ASCII删除和

发表于 分类于 阅读次数： Waline： 本文字数： 764 阅读时长 ≈ 3 分钟

考点

  • LCS

思路

一、问题概述

给定两个字符串 \(s_1\) 与 \(s_2\)，允许对任意一个字符串执行删除字符操作。 每次删除字符的代价等于该字符的 ASCII 值。

目标是：

通过若干次删除操作，使两个字符串最终相同，并使 删除字符的 ASCII 值之和最小。

二、动态规划建模

1. 状态定义

设二维数组： \[ f[i][j] \] 表示：

将字符串 \[ s_1[0 \dots i-1] \quad \text{和} \quad s_2[0 \dots j-1] \] 通过删除操作变成完全相同字符串所需要付出的 最小 ASCII 删除和。

最终答案即为： \[ f[n_1][n_2] \] 其中 \(n_1 = |s_1|\)，\(n_2 = |s_2|\)。

三、初始值（边界条件）

1. 两个字符串都为空

\[ f[0][0] = 0 \]

无需删除任何字符，代价为 0。

2. 其中一个字符串为空

  • 当 \(s_2\) 为空，只能删除 \(s_1\) 的前 \(i\) 个字符：

\[ f[i][0] = \sum_{k=0}^{i-1} \text{ASCII}(s_1[k]) \]

代码实现为前缀递推：

1
f[i][0] = f[i - 1][0] + s1[i - 1];
  • 当 \(s_1\) 为空，只能删除 \(s_2\) 的前 \(j\) 个字符：

\[ f[0][j] = \sum_{k=0}^{j-1} \text{ASCII}(s_2[k]) \]

对应代码为：

1
f[0][j] = f[0][j - 1] + s2[j - 1];

四、状态转移方程

对于一般位置 \((i, j)\)，考虑当前字符：

  • \(s_1[i-1]\)
  • \(s_2[j-1]\)

情况 1：当前字符相同

若： \[ s_1[i-1] = s_2[j-1] \] 则无需删除该字符，直接继承之前的最优状态： \[ f[i][j] = f[i-1][j-1] \]

情况 2：当前字符不同

若： \[ s_1[i-1] \neq s_2[j-1] \] 则必须删除其中一个字符，取两种方案的最小值：

  1. 删除 \(s_1[i-1]\)

\[ f[i-1][j] + \text{ASCII}(s_1[i-1]) \]

  1. 删除 \(s_2[j-1]\)

\[ f[i][j-1] + \text{ASCII}(s_2[j-1]) \]

因此状态转移为： \[ f[i][j] = \min \begin{cases} f[i-1][j] + \text{ASCII}(s_1[i-1]) \\ f[i][j-1] + \text{ASCII}(s_2[j-1]) \end{cases} \]

五、答案的含义

\[ \boxed{f[n_1][n_2]} \]

表示将完整字符串 \(s_1\) 与 \(s_2\) 通过删除操作变为相同字符串时，所需支付的 最小 ASCII 删除和。

六、完整代码（含注释）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    static const int maxn = 1e3 + 5;

    int minimumDeleteSum(string s1, string s2) {
        int n1 = s1.size(), n2 = s2.size();
        int f[maxn][maxn];

        // 初始状态：两个空串
        f[0][0] = 0;

        // s2 为空，只能删除 s1
        for (int i = 1; i <= n1; ++i)
            f[i][0] = f[i - 1][0] + s1[i - 1];

        // s1 为空，只能删除 s2
        for (int j = 1; j <= n2; ++j)
            f[0][j] = f[0][j - 1] + s2[j - 1];

        // 状态转移
        for (int i = 1; i <= n1; ++i) {
            for (int j = 1; j <= n2; ++j) {
                if (s1[i - 1] == s2[j - 1]) {
                    // 当前字符相同，不需要删除
                    f[i][j] = f[i - 1][j - 1];
                } else {
                    // 删除 s1[i-1] 或 s2[j-1]
                    f[i][j] = min(
                        f[i - 1][j] + s1[i - 1],
                        f[i][j - 1] + s2[j - 1]
                    );
                }
            }
        }

        // 最终答案
        return f[n1][n2];
    }
};

七、小结

  • 本题是 经典 LCS 思想的“代价版本”

  • 核心在于：

    • 状态语义要严格限定为“前缀”
    • 边界必须使用前缀累加，而非未初始化值

  • 时间复杂度： \[ O(n_1 \times n_2) \]

  • 空间复杂度： \[ O(n_1 \times n_2) \]