LeetCode LCR 097. 不同的子序列
题目描述
题意分析
从
s中删去若干字符，使剩下的字符按原顺序恰好组成t，统计有多少种选择方式。方案按保留的下标区分，即使最终字符串相同，使用了不同位置也算不同方案。处理一个来源字符时，只有“跳过它”与“用它匹配目标的下一个字符”两种选择。不同历史只要处理了相同的来源前缀、匹配了相同长度的目标前缀，后续选择就相同，可以把方案数合并。
解法：倒序累计目标前缀方案
核心思路
[!blue]
先定义二维状态
f[i][j]：用s的前i个字符组成t前j个字符的方案数。空目标只有一种选择，即不保留任何字符，所以f[i][0] = 1；空来源无法组成非空目标，其余初值为零。若
s[i - 1]与t[j - 1]不同，当前来源字符不能用于目标末位，只能跳过，方案数是f[i - 1][j]。若相同，还可以用当前字符接在较短目标的匹配后面，新增f[i - 1][j - 1]种，因此两项相加。两类方案分别不使用、使用当前来源下标，互不重叠，也覆盖了全部可能。这里必须累加，不能用新方案覆盖旧方案，更不能只记录是否可行。
用一维
dp[j]保存当前已扫描来源前缀对应的方案数。每读入一个s[i]，从目标末尾向前更新；字符相同时执行dp[j] += dp[j - 1]，不同则保留原值。倒序保证dp[j - 1]仍属于加入当前字符之前，避免同一来源字符在本轮匹配多个目标位置。题目保证最终答案在 32 位整数范围内，但不保证所有中间前缀计数都小。若一个中间状态能继续补成完整
t，其中每种前缀选法都能接上同一组后续下标，所以它的计数不会超过最终答案，真正影响结果的状态不会溢出。更大的计数只能属于无法补全的状态，没有通向最终结果的转移路径；Java 的long只是扩大中间量程，不等于任意精度。
解题步骤
- 创建长度为
t.length + 1的零数组，令dp[0] = 1，作为空目标的唯一匹配方式。- 从左到右读取
s的字符，内层从完整目标长度倒序扫描到1。- 当前字符等于
t[j - 1]时，把旧的dp[j - 1]加到dp[j]；否则不修改该状态。- 返回完整目标对应的
dp[t.length]。s比t短时无法完成足够多次匹配，结果自然为零；dp[0]始终保留为一。
代码实现
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++) {
for (int j = t.length(); j >= 1; j--) {
if (s.charAt(i) == t.charAt(j - 1)) {
// 当前字符可以作为 t[j-1]，方案来自更短目标前缀。
dp[j] += dp[j - 1];
}
}
}
return (int) dp[t.length()];
}
}
func numDistinct(s string, t string) int {
dp := make([]int, len(t)+1)
dp[0] = 1
for i := 0; i < len(s); i++ {
for j := len(t); j >= 1; j-- {
if s[i] == t[j-1] {
// 倒序更新保证当前 s[i] 只使用一次。
dp[j] += dp[j-1]
}
}
}
return dp[len(t)]
}
复杂度分析
- 时间复杂度：$O((m + 1)(n + 1))$，其中
m、n是来源与目标长度，包含边界初始化。- 空间复杂度：$O(n + 1)$，保存一行目标前缀方案数。
关键点总结
[!green]
- 计数对象是来源下标的选择方式，不对最终相同的字符串去重。
- “用当前字符”和“不用当前字符”是互斥分类，所以方案数相加。
- 倒序读取上一轮的较短目标计数，保证每个来源字符最多使用一次。
dp[0] = 1是计数递推的起点，不能因目标为空而初始化为零。
易错点总结
[!yellow]
- dp[0]=1 表示空目标有一种匹配方式；其他状态从 0 开始。
- 目标下标倒序更新，确保当前来源字符最多用一次；匹配时累加而不是覆盖。
- 按保留的下标方案计数，不对相同结果字符串去重。
- 题目只保证最终答案范围；若变体要求任意大的精确计数，需要大整数，不能依赖 long 容纳所有组合数。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1143. 最长公共子序列 | 中等 | 同样处理两个前缀的匹配关系，原题取最大长度，本题在匹配时累加选与不选的方案数。 |