940. 不同的子序列 II

发表于 2026-01-28 分类于力扣阅读次数： Waline：本文字数： 2.6k 阅读时长 ≈ 9 分钟

考点

线性DP

思路

1. 题目与目标

给定一个仅由小写字母组成的字符串 \(s\)，需要计算它的 不同的非空子序列 的个数，并对 \(10^9 + 7\) 取模。

关键点：

子序列不要求连续，但要保持原有相对顺序。
“不同”只看字符串内容，不关心选的是哪几个下标。
结果非常大，需要取模。

2. 子序列的构造：每一步到底发生了什么？

设：

用 \(S_i\) 表示由前 \(i\) 个字符 \(s[1..i]\) 构成的 所有不同非空子序列的集合。
最终答案是 \(|S_n|\)。

假设当前已经处理完前 \(i-1\) 个字符，已经得到集合 \(S_{i-1}\)。现在处理第 \(i\) 个字符，记为 \(s[i] = c\)。

2.1 子序列的两种来源

任何属于 \(S_i\) 的子序列，只可能有两种来源：

不使用第 \(i\) 个字符 这时子序列完全来自 \(S_{i-1}\)。
使用第 \(i\) 个字符 这时子序列的末尾一定是 \(c\)，可以写成：
- 先选一个旧子序列 \(x \in S_{i-1}\)，然后接上当前字符 \(c\)：得到 \(x c\)
- 或者前面什么都不选，直接只选当前字符 \(c\)：得到 "c" 这一种子序列

因此可以定义一个“候选集合”： \[ B_i = \{ x c \mid x \in S_{i-1} \} \cup \{ c \} \] 新的子序列集合满足： \[ S_i = S_{i-1} \cup B_i \]

2.2 真正的难点：如何处理“重复”？

在上式中，\(S_{i-1}\) 和 \(B_i\) 可能有交集： \[ S_{i-1} \cap B_i \neq \varnothing \] 也就是说，有一些子序列既属于旧集合，又被“选当前字符 \(c\)”再次生成了一次，这就是重复，需要在计数时扣除。

问题变成：

交集 \(S_{i-1} \cap B_i\) 里，到底是哪些子序列？

3. 关键等价：交集 = “旧集合中以当前字符结尾的子序列”

注意两点：

按照定义，候选集合 \(B_i\) 中的所有元素都形如 \(x c\)，因此 它们的最后一个字符一定是 \(c\)。
交集 \(S_{i-1} \cap B_i\) 要求元素既在 \(S_{i-1}\) 中，又在 \(B_i\) 中。但在 \(B_i\) 中的所有串都以 \(c\) 结尾，所以交集中的所有串也必须以 \(c\) 结尾。

于是可以得到非常重要的一点： \[ S_{i-1} \cap B_i = \{\, w \in S_{i-1} \mid \text{最后一个字符是 } c \,\} \] 结论：

在处理第 \(i\) 个字符 \(c\) 时，本轮产生的重复子序列，恰好就是“旧集合中所有以 \(c\) 结尾的不同子序列”。

这句话是整个题目的核心。

4. 例子：用 `accc` 看一眼重复长什么样

考虑字符串 accc。

依次写出各前缀产生的不同非空子序列集合：

a \[ S_1 = \{ "a" \} \]
ac 新增来自使用 c：
- "" + c = "c"
- "a" + c = "ac"
得到： \[ S_2 = \{ "a", "c", "ac" \} \]
acc 旧集合： \[ S_2 = \{ "a", "c", "ac" \} \] 候选（使用第二个 c）：
- "a" + c = "ac"
- "c" + c = "cc"
- "ac" + c = "acc"
- "" + c = "c"
所以： \[ B_3 = \{ "ac", "cc", "acc", "c" \} \] 交集： \[ S_2 \cap B_3 = \{ "c", "ac" \} \] 这些恰好是旧集合中 以 c 结尾的子序列："c", "ac"。
accc 旧集合： \[ S_3 = \{ "a", "c", "ac", "cc", "acc" \} \] 候选（使用第三个 c）：
- "a" + c = "ac"
- "c" + c = "cc"
- "ac" + c = "acc"
- "cc" + c = "ccc"
- "acc" + c = "accc"
- "" + c = "c"
即： \[ B_4 = \{ "ac", "cc", "acc", "ccc", "accc", "c" \} \] 交集： \[ S_3 \cap B_4 = \{ "c", "ac", "cc", "acc" \} \] 这些恰好是旧集合中，以 c 结尾的子序列。

从这个例子可以直观看出：

每一步的重复部分，确实就是上一轮旧集合中以当前字符结尾的那一批子序列。

下面所有 DP 建模都围绕这一点展开。

5. 解法一：按“结尾字符”分类（26 状态 DP）

这是最直观、最适合教学的解法。

5.1 状态设计

维护两类量：

res：当前前缀的 不同非空子序列的总数；
f[ch]：当前前缀中，以字母 ch 结尾的不同非空子序列的数量。

显然： \[ res = \sum_{ch = 'a'}^{'z'} f[ch] \]

5.2 转移推导

当前处理的字符是 c。

不选 c：什么都不变；
选 c：
- 对于每个旧子序列（共有 res 个），在末尾接一个 c，得到 res 个候选；
- 再加上单独的 "c" 这个子序列，多 1 个候选。
因此，本轮“使用当前 c”产生的候选总数为： \[ \text{候选数} = res + 1 \]
在这些候选中，会“重复”的，恰恰是旧集合中已经以 c 结尾的那些子序列，数量是 f[c]。

因此， \[ \text{新增} = (res + 1) - f[c] \]
更新：
- 以 c 结尾的子序列数量增加 新增： \[ f[c] \leftarrow f[c] + \text{新增} \]
- 总数量也增加 新增： \[ res \leftarrow res + \text{新增} \]

所有运算均需对模数取模，并且注意处理负数。

5.3 时间与空间复杂度

时间复杂度：遍历字符串一次，每步 \(O(1)\)，整体 \(O(n)\)；
空间复杂度：使用 26 长度的数组，整体 \(O(1)\)。

5.4 对应实现（带详细注释）

class Solution {
public:
    static const int mod = 1e9 + 7;

    int distinctSubseqII(string s) {
        long long res = 0;      // 当前前缀的不同“非空”子序列总数
        long long f[26] = {};   // f[p]: 当前前缀中，以字母 'a' + p 结尾的不同非空子序列数量

        for (char c : s) {
            int p = c - 'a';

            // 本轮如果“使用当前字符 c”：
            //   所有旧子序列后接 c：res 个
            //   单独 "c"：1 个
            // 候选总数 = res + 1
            //
            // 其中重复的，是旧集合中已经以 c 结尾的子序列：共有 f[p] 个
            // 因此真正新增的数量：
            long long add = (res + 1 - f[p] + mod) % mod;

            // 以 c 结尾的子序列增加 add 个
            f[p] = (f[p] + add) % mod;

            // 总的不同非空子序列也增加 add 个
            res = (res + add) % mod;
        }

        // res 就是完整字符串的不同非空子序列数量
        return (int)res;
    }
};

6. 解法二：全局 DP + “最后一次出现”规范化表示

第二种解法不再显式维护“以哪个字符结尾”，而是利用“最后一次出现位置”把重复部分压缩成一个更简单的量。

这一部分的逻辑相对抽象一些，适合已经接受了解法一之后，作为“高阶版本”。

6.1 新的状态定义：包含空串

令：

\(T_i\)：用前 \(i\) 个字符 \(s[1..i]\) 能形成的 所有不同子序列的集合，包含空串；
\(F[i] = |T_i|\)。

初始条件： \[ F[0] = 1 \] （只有空串）

由于题目只要求非空子序列，所以最终答案是： \[ \text{Ans} = F[n] - 1 \]

6.2 如果完全不考虑重复会怎样？

每个旧子序列在面对新字符时，有两种选择：

不选
选

因此，如果完全不考虑重复，应该有： \[ F[i] = 2 F[i-1] \] 真实情况中会出现重复，需要扣掉一部分。

6.3 如何数“旧集合中以 c 结尾”的子序列？（核心规范化思想）

仍然设当前字符为 \(c = s[i]\)。记 \(j\) 为字符 \(c\) 在位置 \(i\) 之前 最后一次出现的位置。若此前从未出现过，则令 \(j = 0\)。

接下来考虑这件事：

旧集合中所有 以 \(c\) 结尾的不同子序列，到底有多少个？

设这个集合为： \[ A = \{\, w \in T_{i-1} \mid w \text{ 以 } c \text{ 结尾} \,\} \] 对其中任意一个字符串 \(w \in A\)，都可以写成： \[ w = u \cdot c \] 其中 \(u\) 是某个子序列（可能为空）。

关键观察是：

在位置 \(i\) 之前，最后一次出现字符 \(c\) 的位置是 \(j\)；
在子序列的层面，不关心选的是哪一个具体的位置，只关心最终组成的字符串；
对于字符串 \(w\)，即使它原本是通过某个更早的 c 构造出来的，也可以重新选择使用位置 \(j\) 的 c 作为最后一位，只要前面的前缀字符都位于 \(1..j-1\) 区间内；
因此，对于每一个以 c 结尾的字符串 \(w\)，可以选择一种实现方式，让它的最后一个 c 恰好来自位置 \(j\)。

这等价于：每个 \(w \in A\) 都可以唯一写成： \[ w = u \cdot c, \quad \text{其中 } u \in T_{j-1} \] （\(u\) 是前 \(j-1\) 个字符构成的某个子序列，允许为空）

于是就得到一个非常重要的一一对应：

从左到右：对于每个 \(u \in T_{j-1}\)，构造 \(u c\)，得到一个以 \(c\) 结尾的子序列；
从右到左：对于每个以 \(c\) 结尾的子序列 \(w\)，唯一地对应到一个 \(u\)，即去掉最后一个字符 \(c\) 得到前缀。

因此存在双射： \[ u \in T_{j-1} \quad \longleftrightarrow \quad u c \in A \] 于是可以得到： \[ |A| = |T_{j-1}| = F[j-1] \] 这句话就是：

旧集合中，以 \(c\) 结尾的不同子序列的个数 = 前 \(j-1\) 个字符构成的不同子序列（包含空串）的个数。

这才是第二种解法中，F[j-1] 出现的根本原因。

6.4 将重复纳入递推

由于：

如果忽略重复，有 \(2 F[i-1]\) 种子序列；
其中重复部分的数量是 \(|A| = F[j-1]\)；

所以：

当 \(j = 0\)（当前字符 \(c\) 首次出现）时，没有重复： \[ F[i] = 2 F[i-1] \]
当 \(j > 0\) 时，需要扣掉这 \(F[j-1]\) 个重复： \[ F[i] = 2 F[i-1] - F[j-1] \]

最终，非空子序列个数为： \[ \text{Ans} = F[n] - 1 \]

6.5 时间与空间复杂度

时间复杂度：\(O(n)\)；
空间复杂度：\(O(n + 26)\)（用于 F 和 last 数组）。

6.6 AC代码

class Solution {
public:
    static const int mod = 1e9 + 7;

    int distinctSubseqII(string s) {
        int n = s.size();
        int pre[2050] = {};   // pre[i]: 第 i 个字符上一次出现的位置（1-based），0 表示从未出现
        int pos[26] = {};     // pos[c]: 字母 c 最近一次出现的位置（1-based）

        // 预处理每个位置的上一次出现位置 pre[i]
        for (int i = 1; i <= n; ++i) {
            int c = s[i - 1] - 'a';
            pre[i] = pos[c];   // 第 i 个字符以前最近一次出现的位置
            pos[c] = i;        // 更新当前字符的位置
        }

        long long F[2050] = {};
        // F[i]: 前 i 个字符的不同子序列数量（包含空串）
        F[0] = 1; // 只有空串

        for (int i = 1; i <= n; ++i) {
            int j = pre[i]; // 当前字符上一次出现的位置

            // 如果从未出现过（j == 0），则没有重复：F[i] = 2 * F[i-1]
            // 如果出现过，需要减去 F[j-1]：F[i] = 2 * F[i-1] - F[j-1]
            long long sub = (j == 0 ? 0 : F[j - 1]);
            F[i] = (2 * F[i - 1] % mod - sub + mod) % mod;
        }

        // F[n] 包含空串，题目要求非空子序列，因此需要减去 1
        return (int)((F[n] - 1 + mod) % mod);
    }
};

考点

思路