LeetCode 115. 不同的子序列
题目描述
题意分析
从源字符串
s中删除任意个字符，保留其余字符的相对顺序，使得到的字符串恰好等于目标t，统计一共有多少种选择方法。保留的字符不要求在s中连续，但不能改变顺序，也不能重复使用同一个位置。计数区分的是从
s中选了哪些下标。即使得到的字符内容完全相同，只要下标选择不同，仍然是不同方案。目标串比源串长时不可能组成，答案为零；最终答案是方案数量，不是最长匹配长度。
解法：一维前缀计数动态规划
核心思路
[!blue]
先从二维状态理解：
ways[i][j]表示从s的前i个字符中，选出t的前j个字符的方案数。考虑最新加入的源字符s[i - 1]，所有方案可以按是否使用这个具体位置分成互不重叠的两类。不使用它时，仍从前
i - 1个源字符组成前j个目标字符，贡献ways[i - 1][j]。使用它时，由于它是目前最靠后的源位置，只能匹配目标前缀的最后一个字符t[j - 1]；两字符相等才有这一类，其余部分贡献ways[i - 1][j - 1]。因此匹配时将两类相加，不匹配时只保留第一类，不会重复或漏计方案。边界是
ways[i][0] = 1：无论源前缀多长，组成空目标都只有“全部不选”这一种方法。没有源字符却要组成非空目标时，方案数为零。这是后续计数能够从空选择逐步扩展的起点。每一行只依赖上一行，可以压缩成
dp[j]。处理当前源字符前，dp[j]保存旧行；相等时执行dp[j] += dp[j - 1]，不等时不改动。为了让右边的dp[j - 1]仍属于上一行，j必须从大到小更新。若反过来更新，刚写入的状态又会被读取，相当于同一个源字符在本轮被使用多次。处理了
i + 1个源字符后，最多只能组成同样长度的目标前缀，所以代码从min(i + 1, t.length())开始倒序遍历。扫描结束时，dp[t.length()]就统计了整个源串组成完整目标串的所有方案。
解题步骤
- 创建长度为
t.length() + 1的计数数组，令dp[0] = 1，其余状态为零。- 依次枚举源字符
s[i]，本轮可处理的目标长度上限为min(i + 1, t.length())。- 从上限倒序枚举
j到一，比较s[i]与t[j - 1]。- 字符相等时，把旧的
dp[j - 1]加到dp[j]；不相等时保留dp[j]，表示跳过当前源字符。- 始终保持
dp[0] = 1，最后返回dp[t.length()]。
代码实现
class Solution {
public int numDistinct(String s, String t) {
long[] dp = new long[t.length() + 1];
dp[0] = 1;
for (int i = 0; i < s.length(); i++) {
int upper = Math.min(i + 1, t.length());
// 倒序更新让左边仍是旧前缀状态，避免同一源字符重复使用。
for (int j = upper; j >= 1; j--) {
if (s.charAt(i) == t.charAt(j - 1)) {
// 匹配时增加选当前字符的方案，原值保留不选它的方案。
dp[j] += dp[j - 1];
}
}
}
return (int) dp[t.length()];
}
}
func numDistinct(s string, t string) int {
dp := make([]int64, len(t)+1)
dp[0] = 1
for i := 0; i < len(s); i++ {
upper := len(t)
if i+1 < upper {
upper = i + 1
}
// 倒序更新让左边仍是旧前缀状态，避免同一源字符重复使用。
for j := upper; j >= 1; j-- {
if s[i] == t[j-1] {
// 匹配时增加选当前字符的方案，原值保留不选它的方案。
dp[j] += dp[j-1]
}
}
}
return int(dp[len(t)])
}
复杂度分析
- 时间复杂度：
O(mn)，其中m、n分别为源串和目标串长度。每个源字符至多更新n个目标前缀状态。- 空间复杂度：
O(n)。只保留目标前缀长度这一维，二维状态用于推导，并不实际创建。
关键点总结
[!green]
- 计数对象是源下标的选择方法，重复字符仍可能带来不同方案。
- 按是否使用当前源位置分类，两类互斥且覆盖所有选择，匹配时应当相加。
- 空目标的一种空选择提供起始计数；倒序更新保证每个源位置最多使用一次。
- 先说明二维状态，再压缩为一维，才能明确每次读取属于哪一轮。
易错点总结
[!yellow]
- 按子串处理：跳过源串中的字符完全合法，不能要求选择的位置连续。
- 把
dp[0]初始化为零：空选择是后续匹配的来源，缺少它会使所有计数都保持为零。- 从小到大更新：会读取本轮已经累加的左侧状态，重复使用当前源字符，应从大到小更新。
- 字符相等时直接赋值为
dp[j - 1]：会丢掉不使用当前字符的已有方案，正确操作是累加。- 字符不等时将
dp[j]清零：仍然可以跳过当前源字符，旧方案应全部保留。- 把目标长度当成末尾下标：状态长度为
j，需要比较的是t[j - 1]。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1143. 最长公共子序列 | 中等 | 同样处理两个前缀的匹配关系，原题取最大长度，本题在匹配时累加选与不选的方案数。 |