3316. 从原字符串里进行删除操作的最多次数

发表于 分类于 阅读次数： Waline： 本文字数： 1.2k 阅读时长 ≈ 4 分钟

考点

  • LCS

思路

动态规划算法讲义（前缀视角）

一、问题抽象

给定：

  • 字符串 source，长度为 \(n\)
  • 字符串 pattern，长度为 \(m\)，且保证 pattern 是 source 的子序列
  • 一个下标集合 targetIndices，表示 允许删除的 source 下标（删除不改变索引）

目标：

在保证 pattern 仍然是删除后字符串子序列的前提下， 最大化删除操作的次数。

二、核心建模思想

本题的关键不在于“枚举删除方案”，而在于：

在子序列匹配的过程中，动态决定每个字符是： 删除 / 保留但不匹配 / 用来匹配 pattern

因此，自然采用 前缀型动态规划（Prefix DP）。

三、状态定义（State Definition）

定义二维 DP： \[ f[i][j] = \begin{cases} \text{在只考虑 } source[0 \dots i-1] \text{ 的前提下，} \\ \text{已经使 } pattern[0 \dots j-1] \text{ 成为子序列时，} \\ \text{最多可以删除的字符个数} \end{cases} \] 其中：

  • \(0 \le i \le n\)
  • \(0 \le j \le m\)

四、初始值（Initialization）——最易出错点

1. 不可达状态必须是「负无穷」

由于本题是 最大化问题，所有“不可能到达”的状态必须初始化为一个极小值： \[ \text{NEG} \ll 0 \quad (\text{例如 } -10^9) \] 否则在取 max 时，会错误地被选中。

2. 唯一合法起点

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

含义：

  • 尚未处理任何字符
  • 尚未匹配任何 pattern
  • 删除次数为 0

3. 为什么 f[i][0] 必须显式初始化

状态 \(f[i][0]\) 表示：

在 source 的前 \(i\) 个字符中， 尚未匹配 pattern 的任何字符，最多能删多少个。

这是后续所有匹配的“根基状态”。

如果不正确初始化：

  • 就无法在匹配 pattern 第一个字符之前， 合法地删除或跳过 source 的前缀
  • 会直接导致答案偏小甚至错误

因此有： \[ f[i][0] = \text{前 } i \text{ 个 source 字符中，可删除位置的个数} \]

五、状态转移方程（Transition）

考虑第 \(i\) 个字符 source[i-1]，对状态 \(f[i-1][j]\) 有三种选择：

1. 不删除，不用于匹配（跳过）

\[ f[i][j] \gets \max(f[i][j], f[i-1][j]) \]

含义： 保留当前字符，但不用于匹配 pattern[j]。

2. 删除当前字符（若允许）

若 \(i-1 \in targetIndices\)，则： \[ f[i][j] \gets \max(f[i][j], f[i-1][j] + 1) \]

3. 用于匹配 pattern

若：

  • \(j \ge 1\)
  • \(source[i-1] = pattern[j-1]\)

则： \[ f[i][j] \gets \max(f[i][j], f[i-1][j-1]) \]

总转移公式

\[ f[i][j] = \max \begin{cases} f[i-1][j] & \text{（跳过）} \\ f[i-1][j] + 1 & \text{（删除，若可删）} \\ f[i-1][j-1] & \text{（匹配，字符相等）} \end{cases} \]

六、答案（Answer）

最终答案即为： \[ \boxed{f[n][m]} \] 含义：

  • 已处理完整个 source
  • 已匹配完整个 pattern
  • 在所有合法方案中，删除次数最大

七、二维 DP 代码（注释版）

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
40
41
42
43
44
45
46
47
class Solution {
public:
    static const int maxn = 3005;
    // 负无穷，用于表示不可达状态（max DP 必须用极小值）
    static const int neg = 0xcfcfcfcf;

    int maxRemovals(string source, string pattern, vector<int>& targetIndices) {
        int n1 = source.size(), n2 = pattern.size();

        // f[i][j]: 前 i 个 source，匹配前 j 个 pattern，最大删除次数
        int f[maxn][maxn];
        memset(f, 0xcf, sizeof(f));  // 初始化为 neg

        // mp[i] = true 表示 source[i] 允许删除
        bool mp[maxn];
        memset(mp, 0, sizeof(mp));
        for (int x : targetIndices) mp[x] = true;

        // 初始状态
        f[0][0] = 0;

        // 初始化 f[i][0]：尚未匹配任何 pattern
        for (int i = 1, s = 0; i <= n1; ++i) {
            if (mp[i - 1]) s++;   // 可删位置累加
            f[i][0] = s;
        }

        // 状态转移
        for (int i = 1; i <= n1; ++i) {
            for (int j = 1; j <= n2; ++j) {
                // 1. 不删、不匹配
                f[i][j] = f[i - 1][j];

                // 2. 删除当前字符
                if (f[i - 1][j] != neg && mp[i - 1])
                    f[i][j] = max(f[i][j], f[i - 1][j] + 1);

                // 3. 匹配 pattern[j-1]
                if (f[i - 1][j - 1] != neg &&
                    source[i - 1] == pattern[j - 1])
                    f[i][j] = max(f[i][j], f[i - 1][j - 1]);
            }
        }

        return f[n1][n2];
    }
};

八、滚动数组优化版（注释版）

空间优化： 将 f[i][*] 压缩为一维数组，j 必须倒序遍历，以防覆盖上一行数据。

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
40
41
class Solution {
public:
    static const int maxn = 3005;
    static const int neg = 0xcfcfcfcf;

    int maxRemovals(string source, string pattern, vector<int>& targetIndices) {
        int n1 = source.size(), n2 = pattern.size();

        // f[j]: 当前处理到某个 i 时，匹配前 j 个 pattern 的最大删除次数
        int f[maxn];
        memset(f, 0xcf, sizeof(f));

        bool mp[maxn];
        memset(mp, 0, sizeof(mp));
        for (int x : targetIndices) mp[x] = true;

        f[0] = 0;  // f[0] 表示尚未匹配任何 pattern

        int s = 0; // 累计 f[i][0] 的值

        for (int i = 1; i <= n1; ++i) {
            // j 必须从大到小，防止覆盖 f[j-1]
            for (int j = n2; j >= 1; --j) {
                // 删除当前字符
                if (f[j] != neg && mp[i - 1])
                    f[j]++;

                // 匹配 pattern[j-1]
                if (f[j - 1] != neg &&
                    source[i - 1] == pattern[j - 1])
                    f[j] = max(f[j], f[j - 1]);
            }

            // 更新 f[0]
            if (mp[i - 1]) s++;
            f[0] = s;
        }

        return f[n2];
    }
};