115. 不同的子序列

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

考点

  • LCS

思路

一、问题描述

给定两个字符串：

  • 源字符串：\(s\)，长度为 \(n_1\)
  • 目标字符串：\(t\)，长度为 \(n_2\)

需要统计： 字符串 \(s\) 的不同子序列中，等于 \(t\) 的个数。

若 \(n_1 < n_2\)，显然无解，答案为 0。

二、动态规划建模

1. 状态定义

定义二维 DP 数组： \[ f[i][j] = \text{用 } s \text{ 的前 } i \text{ 个字符，组成 } t \text{ 的前 } j \text{ 个字符的方案数} \] 其中：

  • \(0 \le i \le n_1\)
  • \(0 \le j \le n_2\)

2. 初始条件（Base Case）

  1. 空串匹配空串

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

  1. 任意前缀的 \(s\) 匹配空串

\[ f[i][0] = 1 \quad (1 \le i \le n_1) \]

解释： 目标串为空时，只存在一种方案——什么都不选。

  1. 空串匹配非空目标串

\[ f[0][j] = 0 \quad (j \ge 1) \]

三、状态转移方程

考虑当前字符：

  • \(s[i-1]\)
  • \(t[j-1]\)

情况 1：字符不相等

若 \[ s[i-1] \neq t[j-1] \] 则当前字符无法用于匹配，只能跳过： \[ f[i][j] = f[i-1][j] \]

情况 2：字符相等

若 \[ s[i-1] = t[j-1] \] 此时有两种互斥选择：

  1. 不使用 \(s[i-1]\) 方案数：\(f[i-1][j]\)
  2. 使用 \(s[i-1]\) 匹配 \(t[j-1]\) 方案数：\(f[i-1][j-1]\)

因此： \[ f[i][j] = f[i-1][j] + f[i-1][j-1] \]

四、剪枝优化：状态可达性分析（关键）

1. 剪枝动机

虽然 \(n_1 \ge n_2\) 能保证整体存在解的可能性， 但在 DP 表中，并非所有中间状态 \((i,j)\) 都能走到终点 \((n_1,n_2)\)。

若某个状态从当前位置开始，剩余字符数已经不足以补齐目标串，则该状态对最终答案必然无贡献，应当剪枝。

2. 可达性条件推导

在状态 \((i,j)\)：

  • 已用掉：\(i\) 个字符
  • 剩余可用：\(n_1 - i\)
  • 目标还缺：\(n_2 - j\)

要使该状态仍有可能完成目标，必须满足： \[ n_1 - i \ge n_2 - j \] 等价变形为： \[ j \ge i - (n_1 - n_2) \]

3. 有效状态范围

综合两条必要条件：

  1. 当前合法：

\[ j \le i \]

  1. 未来可达：

\[ j \ge i - (n_1 - n_2) \]

因此在第 \(i\) 行，\(j\) 的合法范围为： \[ \boxed{ \max(1,\, i - (n_1 - n_2)) \le j \le \min(i,\, n_2) } \] 该剪枝在极端情况下（如 \(s\) 与 \(t\) 全为同一字符）可以有效避免中间组合数爆炸，防止整数溢出。

五、答案获取

最终答案即为： \[ \boxed{f[n_1][n_2]} \]

六、算法复杂度

  • 时间复杂度： \[ O(n_1 \times n_2) \quad (\text{剪枝后常数显著降低}) \]

  • 空间复杂度：

    • 二维 DP：\(O(n_1 \times n_2)\)
    • 滚动数组：\(O(n_2)\)

七、参考实现

1. 二维 DP（带可达性剪枝）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    static const int maxn = 1e3 + 5;
    int numDistinct(string s, string t) {
        unsigned long long f[maxn][maxn];
        int n1 = s.size(), n2 = t.size();
        if (n1 < n2)
            return 0;
        memset(f, 0, sizeof(f));
        f[0][0] = 1;
        for (int i = 1; i <= n1; ++i)
            f[i][0] = 1;
        for (int i = 1; i <= n1; ++i) {
            for (int j = max(1, i - n1 + n2); j <= min(n2, i); ++j) {
                if (s[i - 1] != t[j - 1])
                    f[i][j] = f[i - 1][j];
                if (s[i - 1] == t[j - 1])
                    f[i][j] = f[i - 1][j - 1] + f[i - 1][j];
            }
        }
        return f[n1][n2];
    }
};

2. 滚动数组优化（一维 DP）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    static const int maxn = 1e3 + 5;
    int numDistinct(string s, string t) {
        unsigned long long f[maxn];
        int n1 = s.size(), n2 = t.size();
        if (n1 < n2)
            return 0;
        memset(f, 0, sizeof(f));
        f[0] = 1;
        for (int i = 1; i <= n1; ++i) {
            f[0] = 1;
            for (int j = min(n2, i); j >= max(1, i - n1 + n2); --j) {
                if (s[i - 1] != t[j - 1])
                    continue;
                else
                    f[j] += f[j - 1];
            }
        }
        return f[n2];
    }
};