用 Python 编写的查找不同子序列数量的程序

pythonserver side programmingprogramming更新于 2025/12/9 13:32:17

假设我们有一个字符串 s，我们必须计算该字符串 s 的不同子序列的数量。如果答案太大，则返回结果模 10^9 + 7。

因此，如果输入为 s = "bab"，则输出将为 6，因为有 6 个不同的序列，分别是 "a"、"b"、"ba"、"ab"、"bb"、"abb"。

要解决这个问题，我们将遵循以下步骤 −

dp := 一个大小与 s 相同且填充为 0 的数组
m := 10^9 + 7
对于 s 中的每个索引 i 和项目字符，执行
- ind := s 中第 i 个字符的索引正确
- dp[i] := 1 + (dp[从索引 0 到 i-1] 中所有元素之和) mod m 如果 ind 与 -1 相同否则 (dp[从索引 ind 到 i-1] 中所有元素之和) mod m
返回 dp mod m 中所有元素之和

示例

让我们看看下面的实现以便更好地理解

def solve(s):
   dp, m = [0] * len(s), 10**9 + 7
   for i, char in enumerate(s):
      ind = s.rfind(char, 0, i)
      dp[i] = 1 + sum(dp[:i]) % m if ind == -1 else sum(dp[ind:i]) % m
   return sum(dp) % m

s = "bab"
print(solve(s))