题目描述

给定一个字符串 S，计算 S 的不同非空子序列的个数。

因为结果可能很大，所以返回答案模 10^9 + 7。

样例

输入："abc"
输出：7
解释：7 个不同的子序列分别是 "a", "b", "c", "ab", "ac", "bc", 以及 "abc"。

输入："aba"
输出：6
解释：6 个不同的子序列分别是 "a", "b", "ab", "ba", "aa" 以及 "aba"。

输入："aaa"
输出：3
解释：3 个不同的子序列分别是 "a", "aa" 以及 "aaa"。

注意

• S 只包含小写字母。
• 1 <= S.length <= 2000。

算法

(动态规划) $O(n)$

1. 设 $f(i, j)$ 表示遍历了前 $i$ 个字符，其中以字符 $j$ 结尾的不同的子序列的个数。
2. 假设第 $i$ 个字符为 $k$，则 $f(i, k) = 1 + \sum {f(i, j)}$。其中加的 1 是单独以该字符结尾的子序列；这个字符也可以和之前以任意字符结尾的子序列们组合在一起。
3. 初始值 $f(0, j) = 0$，最终答案为 $\sum {f(n, j)}$。
4. 代码实现时，可以将第一维省略，并且用一个变量 $sum$ 来记录当前 $\sum {f(i, j)}$ 的值。

时间复杂度

• 线性遍历一次，故时间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    int distinctSubseqII(string S) {
        int mod = 1000000007;
        int n = S.length(), ans = 0;
        vector<int> f(26, 0);
        int sum = 0;

        for (int i = 0; i < n; i++) {
            int old_f = f[S[i] - 'a'];
            f[S[i] - 'a'] = (sum + 1) % mod;
            sum = (((sum + f[S[i] - 'a']) % mod - old_f) % mod + mod) % mod;
        }

        return sum;
    }
};