LeetCode LCR 097. 不同的子序列

约 9 分钟
文章信息 5 个分类 3 个标签
分类
LeetCode 困难 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
字符串 动态规划 LCR
目录

题目描述

✅ LCR 097. 不同的子序列

题意分析

给两个字符串 s 和 t，问在 s 里有多少种方式删掉若干字符（可以一个都不删）之后，剩下的内容恰好等于 t。这里的「若干」包含零个，剩余字符必须保持原来的相对顺序。

关键在于统计的口径：两种方案是否算不同，看的是被保留下来的下标集合，而不是拼出来的字符串。s = "aab"、t = "ab" 时，保留下标 {0, 2} 和保留下标 {1, 2} 拼出的都是 "ab"，但它们算两种不同方案，答案是 2。这一点决定了本题是计数题而不是判定题。

约束给了两条信号。字符串长度在千级别，说明可以接受长度乘积量级的算法，但不能接受指数级的枚举；题目还保证最终答案落在 32 位有符号整数范围内，这句话反过来提醒：中间过程可能溢出，因为部分前缀的方案数并不一定受这个保证约束。

边界要单独想清楚。t 为空串时，唯一的方式是把 s 全部删光，方案数是 1 而不是 0；s 比 t 短时不可能匹配，答案是 0；s 与 t 完全相同时答案是 1；s 全是同一个字符、t 是它的一段时，答案是组合数，会迅速变得很大。

解法：一维前缀计数动态规划

核心思路

最朴素的想法是枚举 s 的所有子序列再逐个比对，方案数是 $2^{ s }$，长度上百就已经跑不完。稍微聪明一点是递归：设 f(i, j) 表示用 s 的前 i 个字符去凑 t 的前 j 个字符的方案数，每一步要么丢弃 s[i-1]，要么在字符相等时用它去匹配 t[j-1]。这个递归是对的，但同一对 (i, j) 会被重复求解无数次，指数爆炸的根源正在这里。

瓶颈既然是重复子问题，那就把 (i, j) 的结果记下来。关键观察是：s 的某个字符能否被使用，只取决于「已经匹配到 t 的第几位」，与之前具体挑了哪些下标无关。也就是说，「已匹配的 t 前缀长度」就是完整的状态摘要，无后效性成立。

二维状态定义为：f[i][j] 表示只考虑 s 的前 i 个字符时，能凑出 t 前 j 个字符的方案数。转移分两支——s[i-1] != t[j-1] 时这个字符帮不上忙，只能丢弃，f[i][j] = f[i-1][j]；相等时既可以丢弃也可以用它匹配，两类方案互不重叠，f[i][j] = f[i-1][j] + f[i-1][j-1]。初值 f[i][0] = 1（把前 i 个字符全删光是唯一凑出空串的方式），f[0][j] = 0（j > 0 时空的 s 凑不出非空 t）。

再观察转移只依赖上一行，就能压成一维。滚动后的状态定义是：处理完 s 的前 i 个字符后，dp[j] 等于 f[i][j]，即已扫描前缀能凑出 t 前 j 个字符的方案数。 循环不变量是：外层每完成一轮，整个 dp 数组恰好代表「多考虑了一个 s 字符」之后的完整结果，且 dp[0] 恒等于 1。

一维压缩带来一个必须回答的问题：内层为什么倒序。转移里 dp[j] 需要读的 dp[j-1] 是上一行的值。若正序推进，dp[j-1] 已经在本轮被更新成含 s[i] 的新值，再拿去更新 dp[j] 就等于让同一个 s[i] 在一次遍历中匹配了 t 的两个位置，方案数被虚增。倒序时 dp[j-1] 还没轮到更新，读到的仍是上一行的值，语义才正确。

解题步骤

  • 开一个长度为 t.length() + 1 的数组 dp，把 dp[0] 置为 1，其余置为 0。dp[0] = 1 是整个递推的种子：空目标只有「全删」这一种凑法，如果写成 0，后续所有累加都是零乘零，最终必然输出 0。

  • 外层从左到右遍历 s 的每个字符 s[i]，语义是「把 s 的可用字符逐个放进来」。之所以让 s 走外层、t 走内层，是因为一维数组的下标维度必须是 t，被滚掉的那一维只能是 s。

  • 内层从 j = t.length() 递减到 1。倒序的理由如上：保证读到的 dp[j-1] 是不含当前 s[i] 的旧值，从而让每个 s 字符在本轮最多被使用一次。

  • 当 s[i] == t[j-1] 时执行 dp[j] += dp[j-1]。+= 而非 = 是因为「不用 s[i]」的那些方案已经存在 dp[j] 里，需要保留；新增的 dp[j-1] 是「用 s[i] 去匹配 t[j-1]」的方案数。字符不等时不做任何事，等价于 dp[j] = dp[j]，即只能丢弃当前字符。

  • 遍历结束后返回 dp[t.length()]，即用完整个 s 凑出完整 t 的方案数。Java 里数组用 long 存、返回时再强转 int，是为了让中间可能超出 int 的累加值不至于变成负数。

以 s = "aabb"、t = "ab" 走一遍：dp 长度为 3，初始 dp = [1, 0, 0]。

第一轮，s[0] = 'a'。j = 2 时 t[1] = 'b'，与 'a' 不等，跳过；j = 1 时 t[0] = 'a' 相等，dp[1] += dp[0]，即 0 + 1 = 1。本轮结束 dp = [1, 1, 0]，含义是只用 "a" 已能凑出 "a" 一种方式。

第二轮，s[1] = 'a'。j = 2 不等跳过；j = 1 相等，dp[1] += dp[0]，即 1 + 1 = 2。本轮结束 dp = [1, 2, 0]，含义是 "aa" 里有两个下标可以充当 "a"。

第三轮，s[2] = 'b'。j = 2 时 t[1] = 'b' 相等，dp[2] += dp[1]，即 0 + 2 = 2；j = 1 时 t[0] = 'a' 与 'b' 不等，跳过。本轮结束 dp = [1, 2, 2]。这两种方案是保留下标 {0, 2} 与 {1, 2}。

第四轮，s[3] = 'b'。j = 2 相等，dp[2] += dp[1]，即 2 + 2 = 4；j = 1 不等，跳过。本轮结束 dp = [1, 2, 4]。新增的两种是保留下标 {0, 3} 与 {1, 3}。

返回 dp[2] = 4。手工核对：'a' 可选下标 0 或 1，'b' 可选下标 2 或 3，且任一 a 的下标都小于任一 b 的下标，共 2 × 2 = 4 种，与答案一致。倒序的必要性可以用 s = "aa"、t = "aa" 看得更清楚：正序时第一轮 j = 1 先把 dp[1] 抬到 1，紧接着 j = 2 又读到这个刚更新的值把 dp[2] 抬到 1——只有一个 'a' 却凑出了 "aa"，显然错误；倒序则先算 j = 2（此时 dp[1] 仍为 0），结果保持 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(mn)$，其中 m 与 n 分别是 s 和 t 的长度。外层把 s 的每个字符各处理一次，内层对每个字符都把 t 的所有位置扫一遍，每格只做一次比较和一次加法，没有嵌套更深的循环，因此总步数恰好是两者的乘积。

  • 空间复杂度：$O(n)$，只开了一个长度为 n + 1 的一维数组。滚动掉 s 那一维之后，不再需要保存历史行；由于是迭代实现，也不存在与输入规模相关的递归栈开销。

关键点总结

  • 计数型问题的状态定义要落在「方案数」而不是「可行性」上，转移用加法而非取最值。判断能否匹配和统计有多少种匹配，往往共用同一套状态划分，但一个是布尔或运算，一个是求和，混淆了就会写出只判真假的代码。

  • 空集不是零。凡是「删除若干元素后得到目标」这类计数，空目标的方案数必须初始化为 1，因为「什么都不选」本身就是一种合法方案。把这个种子写成 0，整条递推链会全程归零。

  • 二维 DP 压成一维时，内层循环方向由「依赖的是上一行还是本行」决定：依赖上一行的旧值就必须倒序，依赖本行已更新的新值才用正序。这条规则在 0-1 背包与完全背包的对比里是同一件事，本题相当于把每个 s 字符当成一件只能用一次的物品。

  • 转移拆成互斥的两支再相加，是计数不重不漏的保证。本题按「当前字符用不用」划分，两类方案的下标集合必然不同，所以可以直接相加；如果划分标准会让同一方案被数两次，就必须改用容斥。

  • 题目保证最终答案在 int 范围内，不等于中间量也在范围内。计数题应当默认用更宽的类型承接累加，最后再收窄。

  • 面试视角：这题的价值在于讲清「二维状态定义 → 转移方程 → 初值 → 压缩与循环方向」这条完整链路。直接默写一维版本反而危险，因为面试官几乎必问「为什么倒序」和「dp[0] 为什么是 1」；稳妥的做法是先写出二维版并说明每一项含义，再当场推出一维压缩。

易错点总结

  • dp[0] 初始化为 0：s = "abc"、t = "abc" → 所有转移都是在零上累加，最终返回 0，而正确答案是 1。

  • 内层正序遍历 j：s = "aa"、t = "aa" → 第一轮就让唯一的 'a' 同时匹配 t 的两个位置，dp[2] 被提前抬起，最终输出 3，正确答案是 1。

  • 把 dp[j] += dp[j-1] 写成 dp[j] = dp[j-1]：s = "aabb"、t = "ab" → 覆盖掉「不使用当前字符」的旧方案，第四轮 dp[2] 被直接赋成 2 而非累加成 4，结果偏小。

  • 字符不等时显式写 dp[j] = 0：s = "acb"、t = "ab" → 中间那个 'c' 会把已经积累的方案数清空，之后的 'b' 无从累加，输出 0，而正确答案是 1。字符不等时正确的动作是什么都不做。

  • 下标写成 t.charAt(j) 而不是 t.charAt(j - 1)：任意非空输入 → j 取到 t.length() 时越界抛出异常；即使侥幸不越界，比较的也是错位的字符，结果无意义。

  • 内层循环终止条件写成 j >= 0：任意输入 → j = 0 时访问 dp[-1] 与 t.charAt(-1)，直接抛出越界异常。目标前缀长度为 0 的状态是初值，不参与转移。

  • 全程用 int 累加：s 为 500 个 'a'、t 为 250 个 'a' → 中间的组合数远超 int 上限，累加过程发生溢出，dp 里出现负数并一路污染后续状态，输出一个与正确答案无关的值。

  • 误把子序列当成子串：s = "acb"、t = "ab" → 若要求连续，"ab" 在 s 中不出现，会输出 0；本题允许删除中间字符，正确答案是 1。

  • 误按去重后的字符串计数：s = "aa"、t = "a" → 若认为拼出的字符串相同就只算一种，会输出 1；本题按保留的下标集合计数，正确答案是 2。

  • 外层遍历 t、内层遍历 s：s = "aabb"、t = "ab" → 滚动数组的下标维度是 t，把两层循环对调后每轮更新的语义不再是「新增一个 s 字符」，同一个 s 字符会被反复计入，输出偏大。

相似题目

题目 难度 考察点
72. 编辑距离 中等 求最小操作次数，转移取最值且多出替换一支
392. 判断子序列 简单 只判存在性，贪心双指针即可，无需计数
583. 两个字符串的删除操作 中等 两串都可删，求最少删除步数而非方案数
792. 匹配子序列的单词数 中等 一个主串对多个模式串，重点是预处理与分桶
940. 不同的子序列 II 困难 统计本质不同的子序列，需要按末尾字符去重
1143. 最长公共子序列 中等 求公共部分的最大长度，转移取 max 而非求和
LCR 095. 最长公共子序列 中等 与 1143 同题换皮，可用来对照两种转移的写法差异