线性动态规划：计算字符串的不同子序列个数（Count Distinct Subsequences）
字数 2534 2025-12-15 21:03:12

线性动态规划：计算字符串的不同子序列个数（Count Distinct Subsequences）

题目描述

给你一个字符串 s，请你计算它所有不同的非空子序列的个数。
注意：子序列不一定连续，但原字符串中位置不同的相同字符序列视为同一个子序列（即去重）。

示例
输入：s = "abc"
输出：7
解释：所有不同的非空子序列为："a", "b", "c", "ab", "ac", "bc", "abc"，共7个。

输入：s = "aba"
输出：6
解释："a", "b", "ab", "ba", "aa", "aba"，注意 "a" 虽然可以在原字符串中从不同位置得到，但作为一个子序列只算一次。

输入：s = "aaa"
输出：3
解释："a", "aa", "aaa"，其他组合重复不计。

解题思路

这个问题是一个经典的动态规划计数问题，关键在于如何去重。
如果我们简单枚举所有子序列（2^n 个），然后放到集合里去重，时间复杂度会达到 O(2^n)，在 n 较大时不可行。
我们需要一个 O(n) 或 O(n|Σ|) 的解法，其中 |Σ| 是字符集大小。

1. 状态定义

定义 dp[i] 表示考虑前 i 个字符（即 s[0..i-1] 这一段）所构成的不同子序列的个数（包括空子序列）。
注意：这里的“不同”是指内容不同，即使来自不同位置，内容相同的子序列也只算一个。

初始条件：dp[0] = 1，因为只有空子序列。

2. 状态转移的基本想法

假设我们已经知道 dp[i-1] 是前 i-1 个字符的不同子序列个数。
现在我们考虑第 i 个字符 s[i-1]（为了下标方便，字符串从0开始索引，dp 的下标 i 表示长度 i 的前缀）。

不加入新字符：前 i-1 个字符的所有子序列本身也是前 i 个字符的子序列，所以至少包含 dp[i-1] 个。

加入新字符：我们可以在前 i-1 个字符的每一个子序列后面追加字符 s[i-1]，形成新的子序列。
但这里要注意，如果 s[i-1] 以前出现过，那么有些“追加”会重复。

3. 去重逻辑

假设字符 s[i-1] 上一次出现在位置 j-1（0-based，且 j < i），即在处理 s[j-1] 时我们第一次遇到这个字符。
那么，对于前缀 s[0..j-2] 的所有子序列，当我们处理到 s[j-1] 时，已经追加过一次这个字符，生成了一批新的子序列。
现在，当我们再次在位置 i-1 遇到相同字符时，如果我们还允许“在所有前 i-1 个子序列后追加”，那么从位置 j-1 之后到 i-1 之间的那些子序列（它们是在 j-1 之后才产生的）追加 s[i-1] 会与之前 j-1 位置追加的结果重复。

准确地说：
重复的部分正好是“在上一次该字符出现时的前缀的不同子序列个数”，即 dp[last[ch] - 1]，其中 last[ch] 是字符 ch 上一次出现时的长度索引（dp 下标）。

因此，新子序列的数量是 dp[i-1] - dp[last[ch]-1]（如果 last[ch] 存在）。

4. 递推公式

设 last[ch] 表示字符 ch 上一次出现时的 dp 下标（即前缀长度），如果没出现过则为 0。

递推：

dp[i] = dp[i-1] + (dp[i-1] - (last[ch] > 0 ? dp[last[ch]-1] : 0))

简化：

dp[i] = 2 * dp[i-1] - (last[ch] > 0 ? dp[last[ch]-1] : 0)

其中 ch = s[i-1]。

解释：

  • 2 * dp[i-1] 表示不加入新字符（dp[i-1]）和加入新字符到每一个旧子序列（再加 dp[i-1]）。
  • 减去 dp[last[ch]-1] 是为了去掉重复计数，这些重复是在上一次 ch 出现时已经生成的子序列。

5. 边界与初始化

  • dp[0] = 1 表示空子序列。
  • last[ch] 初始化为 0 表示未出现过。
  • 最终答案：dp[n] - 1（减去空子序列）。

6. 举例推导

以 s = "aba" 为例：

  1. 初始：dp[0] = 1，last[a]=0, last[b]=0。

  2. i=1, 字符 'a'：

    • last['a']=0 → 无重复
    • dp[1] = 2*dp[0] - 0 = 2*1 = 2（子序列："", "a"）
    • 更新 last['a']=1

  3. i=2, 字符 'b'：

    • last['b']=0 → 无重复
    • dp[2] = 2*dp[1] - 0 = 2*2 = 4（新增："b", "ab"，当前所有："", "a", "b", "ab"）
    • 更新 last['b']=2

  4. i=3, 字符 'a'：

    • last['a']=1
    • 重复部分 = dp[last['a']-1] = dp[0] = 1
    • dp[3] = 2*dp[2] - dp[0] = 2*4 - 1 = 7（新增："ba", "aa", "aba"，当前共7个不同子序列包括空串）

最终结果：dp[3]-1 = 7-1 = 6，匹配示例。

7. 算法步骤

  1. 初始化 dp[0]=1，last[ch]=0 对所有 ch。
  2. 遍历 i 从 1 到 n：
    • ch = s[i-1]
    • 重复 = (last[ch] > 0) ? dp[last[ch]-1] : 0
    • dp[i] = 2*dp[i-1] - 重复
    • 更新 last[ch] = i
  3. 返回 dp[n] - 1

注意：dp 值可能很大，通常题目要求对一个大质数取模（如 10^9+7），计算时需处理负数取模。

8. 时间复杂度与空间优化

  • 时间：O(n)
  • 空间：O(n) 可优化到 O(|Σ|)，因为 dp 数组只需记录上一个 dp 值，但我们仍需要记录 last 出现位置。

总结

这个问题的核心在于利用上一次相同字符出现时的子序列个数来去重，从而避免用集合存储，直接通过递推得到不同子序列的数量。这是一种很典型的线性 DP 计数技巧，常用于字符串子序列去重统计。

线性动态规划：计算字符串的不同子序列个数（Count Distinct Subsequences） 题目描述 给你一个字符串 s ，请你计算它 所有不同的非空子序列 的个数。 注意 ：子序列不一定连续，但原字符串中位置不同的相同字符序列视为同一个子序列（即去重）。 示例 输入： s = "abc" 输出： 7 解释：所有不同的非空子序列为： "a" , "b" , "c" , "ab" , "ac" , "bc" , "abc" ，共7个。 输入： s = "aba" 输出： 6 解释： "a" , "b" , "ab" , "ba" , "aa" , "aba" ，注意 "a" 虽然可以在原字符串中从不同位置得到，但作为一个子序列只算一次。 输入： s = "aaa" 输出： 3 解释： "a" , "aa" , "aaa" ，其他组合重复不计。 解题思路 这个问题是一个经典的动态规划计数问题，关键在于 如何去重 。 如果我们简单枚举所有子序列（2^n 个），然后放到集合里去重，时间复杂度会达到 O(2^n)，在 n 较大时不可行。 我们需要一个 O(n) 或 O(n|Σ|) 的解法，其中 |Σ| 是字符集大小。 1. 状态定义 定义 dp[i] 表示 考虑前 i 个字符 （即 s[0..i-1] 这一段）所构成的不同子序列的个数（包括空子序列）。 注意 ：这里的“不同”是指内容不同，即使来自不同位置，内容相同的子序列也只算一个。 初始条件： dp[0] = 1 ，因为只有空子序列。 2. 状态转移的基本想法 假设我们已经知道 dp[i-1] 是前 i-1 个字符的不同子序列个数。 现在我们考虑第 i 个字符 s[i-1] （为了下标方便，字符串从0开始索引，dp 的下标 i 表示长度 i 的前缀）。 不加入新字符 ：前 i-1 个字符的所有子序列本身也是前 i 个字符的子序列，所以至少包含 dp[i-1] 个。 加入新字符 ：我们可以在前 i-1 个字符的 每一个 子序列后面追加字符 s[i-1] ，形成新的子序列。 但这里要注意，如果 s[i-1] 以前出现过，那么有些“追加”会重复。 3. 去重逻辑 假设字符 s[i-1] 上一次出现在位置 j-1 （0-based，且 j < i），即在处理 s[j-1] 时我们第一次遇到这个字符。 那么，对于前缀 s[0..j-2] 的所有子序列，当我们处理到 s[j-1] 时，已经追加过一次这个字符，生成了一批新的子序列。 现在，当我们再次在位置 i-1 遇到相同字符时，如果我们还允许“在所有前 i-1 个子序列后追加”，那么 从位置 j-1 之后到 i-1 之间 的那些子序列（它们是在 j-1 之后才产生的）追加 s[ i-1 ] 会与之前 j-1 位置追加的结果重复。 准确地说 ： 重复的部分正好是“在上一次该字符出现时的前缀的不同子序列个数”，即 dp[last[ch] - 1] ，其中 last[ch] 是字符 ch 上一次出现时的长度索引（dp 下标）。 因此，新子序列的数量是 dp[i-1] - dp[last[ch]-1] （如果 last[ ch ] 存在）。 4. 递推公式 设 last[ch] 表示字符 ch 上一次出现时的 dp 下标（即前缀长度），如果没出现过则为 0。 递推： 简化： 其中 ch = s[ i-1 ]。 解释 ： 2 * dp[i-1] 表示不加入新字符（ dp[i-1] ）和加入新字符到每一个旧子序列（再加 dp[i-1] ）。 减去 dp[last[ch]-1] 是为了去掉重复计数，这些重复是在上一次 ch 出现时已经生成的子序列。 5. 边界与初始化 dp[0] = 1 表示空子序列。 last[ch] 初始化为 0 表示未出现过。 最终答案： dp[n] - 1 （减去空子序列）。 6. 举例推导 以 s = "aba" 为例： 初始： dp[0] = 1 ， last[a]=0 , last[b]=0 。 i=1, 字符 'a'： last[ 'a' ]=0 → 无重复 dp[1] = 2*dp[0] - 0 = 2*1 = 2 （子序列： "", "a" ） 更新 last[ 'a' ]=1 i=2, 字符 'b'： last[ 'b' ]=0 → 无重复 dp[2] = 2*dp[1] - 0 = 2*2 = 4 （新增："b", "ab"，当前所有： "", "a", "b", "ab" ） 更新 last[ 'b' ]=2 i=3, 字符 'a'： last[ 'a' ]=1 重复部分 = dp[last['a']-1] = dp[0] = 1 dp[3] = 2*dp[2] - dp[0] = 2*4 - 1 = 7 （新增："ba", "aa", "aba"，当前共7个不同子序列包括空串） 最终结果： dp[3]-1 = 7-1 = 6 ，匹配示例。 7. 算法步骤 初始化 dp[0]=1 ， last[ch]=0 对所有 ch。 遍历 i 从 1 到 n： ch = s[ i-1 ] 重复 = (last[ ch] > 0) ? dp[ last[ ch]-1 ] : 0 dp[ i] = 2* dp[ i-1 ] - 重复 更新 last[ ch ] = i 返回 dp[ n ] - 1 注意：dp 值可能很大，通常题目要求对一个大质数取模（如 10^9+7），计算时需处理负数取模。 8. 时间复杂度与空间优化 时间：O(n) 空间：O(n) 可优化到 O(|Σ|)，因为 dp 数组只需记录上一个 dp 值，但我们仍需要记录 last 出现位置。 总结 这个问题的核心在于 利用上一次相同字符出现时的子序列个数来去重 ，从而避免用集合存储，直接通过递推得到不同子序列的数量。这是一种很典型的线性 DP 计数技巧，常用于字符串子序列去重统计。