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

题目描述
给定一个字符串 s，要求计算其所有不同的非空子序列的个数。由于结果可能很大，通常要求对一个大质数（如 \(10^9+7\)）取模。

注意：子序列是指通过删除原字符串的某些字符（可以不删除）而不改变剩余字符的相对顺序得到的新字符串。例如，字符串 "aba" 的不同子序列包括："a", "b", "ab", "aa", "aba", "ba"，共 6 个（注意 "a" 出现了两次，但只算一个）。

解题思路

这是一个经典的线性动态规划问题，关键在于避免重复计数。我们需要设计一个状态转移方程，使得相同的子序列只被计算一次。

第一步：定义 dp 状态
定义 dp[i] 表示以字符串前 i 个字符（即 s[0..i-1]）形成的所有不同子序列的个数（包括空子序列）。通常为了方便，我们让 dp[0] 表示空字符串对应的子序列个数（即 1，只有空序列）。

第二步：状态转移的直观想法
假设我们已经处理了前 i-1 个字符，得到了所有不同子序列的集合。现在考虑第 i 个字符 c = s[i-1]。我们可以将 c 添加到之前的所有子序列末尾，形成新的子序列。
那么，新的子序列总数似乎应该是：
dp[i] = dp[i-1] (不使用c) + dp[i-1] (使用c，将c追加到每个已有子序列后)
即 dp[i] = 2 * dp[i-1]。

但是，这样会重复计数。例如，s = "aba"，前两个字符 "ab" 的子序列有："", "a", "b", "ab"。
处理第三个字符 'a' 时，若将 'a' 追加到每个已有子序列后，会得到："a", "aa", "ba", "aba"。
其中 "a" 这个子序列在之前已经存在（来自第一个字符 'a'），因此被重复计算了。

第三步：去重的方法
重复发生在：当前字符 c 之前出现过，而之前形成的一些子序列末尾已经追加过 c 了。
具体来说，设 c 上一次出现的位置是 last[c]（索引从 1 开始，表示在 s 中的第几个字符）。
在 last[c] 位置时，我们已经将 c 追加到了前 last[c]-1 的所有子序列后面。
现在，当我们处理到当前位置 i 时，如果再次将 c 追加到前 i-1 个子序列后面，那么前 last[c]-1 个子序列在 last[c] 位置已经追加过 c 了，这次再追加就会产生重复的子序列。

因此，重复的数量正好是 dp[last[c]-1]（即在 last[c] 位置之前形成的子序列个数，这些子序列在 last[c] 位置已经和 c 组合过了）。

第四步：正确的状态转移方程
令 dp[i] 表示前 i 个字符的不同子序列个数（含空序列）。

• 如果当前字符 c = s[i-1] 之前没有出现过（last[c] 未定义），则：
  dp[i] = 2 * dp[i-1]
• 如果当前字符 c 之前出现过，上一次出现的位置是 last[c]，则：
  dp[i] = 2 * dp[i-1] - dp[last[c] - 1]

这是因为，我们要减去那些在 last[c] 位置已经形成的重复子序列（即 dp[last[c]-1] 个）。

第五步：边界条件
dp[0] = 1（只有空序列）。
最终答案需要去掉空序列，所以结果为 dp[n] - 1。

逐步推导示例

以 s = "aba" 为例：

1. 初始化：dp[0] = 1，last 字典记录每个字符最近一次出现的位置（0表示未出现）。

2. 处理第一个字符 'a'（i=1）：

   • last['a'] 未定义（0），所以 dp[1] = 2 * dp[0] = 2。
     子序列集合："", "a"。
   • 更新 last['a'] = 1。

3. 处理第二个字符 'b'（i=2）：

   • last['b'] 未定义（0），dp[2] = 2 * dp[1] = 4。
     新增子序列：将 'b' 追加到 "" 和 "a" 后面，得到 "b", "ab"。
     全部子序列："", "a", "b", "ab"。
   • 更新 last['b'] = 2。

4. 处理第三个字符 'a'（i=3）：

   • last['a'] = 1 已定义，所以：
     dp[3] = 2 * dp[2] - dp[last['a'] - 1] = 2*4 - dp[0] = 8 - 1 = 7。
     新增子序列：将 'a' 追加到当前四个子序列后，得到 "a", "aa", "ba", "aba"，但其中 "a" 已经存在，需要减去重复的 1 个。
     全部不同子序列："", "a", "b", "ab", "aa", "ba", "aba"，共 7 个。
   • 更新 last['a'] = 3。

5. 最终结果（非空子序列个数）：dp[3] - 1 = 6，与示例一致。

算法实现细节

• 因为只需要前一个状态，可以用一个变量 cur 代替 dp[i]，但需要记录每个字符上一次出现时的 dp 值。
• 通常用数组 last[256] 记录字符上次出现时的 dp 值（即 dp[last[c]-1] 的值）。
  实现时，可以直接存储 lastVal[c] = dp[last[c] - 1]，在遇到重复时减去这个值。
• 取模运算中，减法可能出现负数，需要加上模数再取模。

伪代码：

MOD = 1e9+7
n = len(s)
cur = 1  # dp[0] = 1
lastVal = 数组，长度256，初始化为0
for i from 1 to n:
    c = s[i-1]
    next = (2 * cur) % MOD
    if lastVal[c] != 0:
        next = (next - lastVal[c] + MOD) % MOD
    lastVal[c] = cur
    cur = next
result = (cur - 1 + MOD) % MOD
return result

时间复杂度：O(n)，只需遍历字符串一次。
空间复杂度：O(字符集大小)，通常为 O(256) 或 O(26)（如果只有小写字母）。

思考扩展

1. 如果要求输出所有不同的子序列（而不仅仅是计数），该如何做？（通常用回溯+集合去重，但指数复杂度）。
2. 如果字符串很长（n 很大），但字符集很小，如何优化空间？
   ——依然可以用 lastVal 数组，大小只取决于字符集。
3. 如果题目要求不同子序列的个数模一个大质数，为什么减法后要加 MOD 再取模？
   ——为了防止负数取模产生错误结果。

这道题的关键在于利用上一次相同字符出现时的 dp 值来去重，是线性动态规划中巧妙处理重复计数的典型例子。