1. 概述
本文讨论如何计算一个字符串中不同子序列（distinct subsequences）的数量。
我们会先定义问题并举例说明，随后提供两种解法：
- 暴力生成法：通过回溯生成所有子序列并去重，适合小规模数据。
- 动态规划法：使用数学公式和 DP 思想高效计算，适合大规模数据。
2. 问题定义
给定一个字符串 S，我们需要计算其所有不同的子序列的数量。
✅ 子序列定义：从原字符串中删除若干字符（不改变顺序）后得到的新字符串。
示例
输入：S = "ABA"
其所有不同子序列为：
"", "A", "B", "AB", "BA", "AA", "ABA"
共 7 个。
3. 暴力回溯法（Naive Approach）
3.1 思路
- 使用回溯法生成所有可能子序列。
- 用
Set<String>去重。 - 最终集合大小即为不同子序列数。
3.2 实现代码
import java.util.HashSet;
import java.util.Set;
public class SubsequenceCounter {
public static int countDistinctSubsequences(String s) {
Set<String> subsequences = new HashSet<>();
backtrack(s, 0, new StringBuilder(), subsequences);
return subsequences.size();
}
private static void backtrack(String s, int index, StringBuilder curr, Set<String> subsequences) {
if (index == s.length()) {
subsequences.add(curr.toString());
return;
}
// 选择当前字符
curr.append(s.charAt(index));
backtrack(s, index + 1, curr, subsequences);
curr.deleteCharAt(curr.length() - 1); // 回溯
// 不选择当前字符
backtrack(s, index + 1, curr, subsequences);
}
}
3.3 复杂度分析
- 时间复杂度：
O(2^N)，每个字符有两个选择（选或不选） - 空间复杂度：
O(M)，M 是所有子序列的总长度
⚠️ 该方法对长度较大的字符串效率极低，仅适用于教学或小规模数据。
4. 动态规划法（Dynamic Programming Approach）
4.1 思路
我们不生成子序列，而是通过递推公式直接计算不同子序列的数量。
设 dp[i] 表示前 i 个字符组成的字符串中不同子序列的数量。
递推公式如下：
dp[i] = 2 * dp[i - 1] - dp[last[c]]
其中：
c = s.charAt(i - 1)：当前字符last[c]：字符c上一次出现的位置（未出现过为 -1）
为什么减去 dp[last[c]]？
因为当字符 c 再次出现时，新增的子序列中有一部分是重复的。这些重复子序列等于上次出现时的所有子序列加上当前字符。
4.2 实现代码
public class SubsequenceCounterDP {
public static int countDistinctSubsequences(String s) {
int MOD = 1000000007;
int n = s.length();
int[] dp = new int[n + 1];
int[] last = new int[256]; // 假设字符集为 ASCII
dp[0] = 1; // 空子序列
for (int i = 0; i < 256; i++) {
last[i] = -1;
}
for (int i = 1; i <= n; i++) {
char c = s.charAt(i - 1);
dp[i] = (2 * dp[i - 1]) % MOD;
if (last[c] != -1) {
dp[i] = (dp[i] - dp[last[c] - 1] + MOD) % MOD;
}
last[c] = i;
}
return (dp[n] - 1 + MOD) % MOD; // 减去空子序列
}
}
4.3 复杂度分析
- 时间复杂度：
O(N)，每个字符只处理一次 - 空间复杂度：
O(N + A)，其中 A 是字符集大小（如 256）
✅ 该方法在时间和空间上都更高效，适合处理大规模字符串。
5. 总结
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 暴力回溯法 | O(2^N) | O(M) | 小规模数据 |
| 动态规划法 | O(N) | O(N + A) | 大规模数据 ✅ |
关键点回顾
- 子序列是不连续但保持顺序的字符序列。
- 暴力法简单直观但效率低。
- 动态规划法通过递推公式高效计算，避免了重复生成子序列。
- 用
last[]数组记录字符上次出现位置，用于去重。
✅ 推荐使用动态规划法解决此类问题。