题目描述：LeetCode-940. 不同的子序列 II【字符串，动态规划】

给定一个字符串 s，计算 s 的 不同非空子序列 的个数。因为结果可能很大，所以返回答案需要对 10^9 + 7 取余 。

字符串的 子序列 是经由原字符串删除一些（也可能不删除）字符但不改变剩余字符相对位置的一个新字符串。

例如，“ace” 是 “abcde” 的一个子序列，但 “aec” 不是。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

1 <= s.length <= 2000
s 仅由小写英文字母组成

解题思路一：细分问题，改为分别统计以 ‘a’,‘b’,⋯,‘z’ 结尾的不同子序列的个数，问题就迎刃而解了。每当遍历到下一个字母s[i]就更新以s[i]结尾的f[s[i]]的大小，其他不变。

例如：
aba
数组更新过程：
1 0
1 2
4 2
最后答案就是4+2=6
第一个数表示以a结尾的子串个数，第二个数表示以b结尾的子串个数…
遍历到第一个字符a更新第一个数为1
遍历到第二个字符b更新第二个数为1+0+1=2
遍历到第三个字符a更新第一个数为1+2+1=4
最终答案为f[n-1]的26个数字之和。

class Solution {
    const int MOD = 1e9 + 7;
public:
    int distinctSubseqII(string s) {
        int n = s.length();
        vector<array<int, 26>> f(n);
        f[0][s[0] - 'a'] = 1;
        for (int i = 1; i < n; ++i) {
            f[i] = f[i - 1];
            f[i][s[i] - 'a'] = accumulate(f[i - 1].begin(), f[i - 1].end(), 1L) % MOD;
        }
        return accumulate(f[n - 1].begin(), f[n - 1].end(), 0L) % MOD;
    }
};

解题思路二：优化。只更新f[s[i]]和其他部分的值

以aba为例:

遍历到a时
others=0;
f[0]=1
total=1

遍历到b时
others=1;
f[1]=2;
total=3;

遍历到a时
others=2;
f[0]=4;
total=6;

最后return total

class Solution {
    const int MOD = 1e9 + 7;
public:
    int distinctSubseqII(string s) {
        int total = 0, f[26]{};
        for (char c : s) {
            c -= 'a';
            int others = total - f[c]; // total 中不含 f[c] 的部分（由于取模的原因，这里的减法可能会产生负数）
            f[c] = 1 + total; // 更新 f[c]
            total = ((f[c] + others) % MOD + MOD) % MOD; // 更新 total，并保证 total 非负
        }
        return total;
    }
};

解题思路三：只需要更新 f[s[i]] 的值

class Solution {
    const int MOD = 1e9 + 7;
public:
    int distinctSubseqII(string s) {
        int f[26]{};
        for (char c : s)
            f[c - 'a'] = accumulate(f, f + 26, 1L) % MOD;
        return accumulate(f, f + 26, 0L) % MOD;
    }
};

时间复杂度：O(n+∣Σ∣)，其中 n 为 s 的长度。
空间复杂度：O(∣Σ∣)其中∣Σ∣ 为字符集合的大小，本题中字符均为小写字母，所以 ∣Σ∣=26|

解题思路三：最终的最简代码

class Solution {
    const int MOD = 1e9 + 7;
public:
    int distinctSubseqII(string s) {
        int total=0,f[26]{};
        for(char c:s){
            c-='a';
            int others=total-f[c];
            f[c]=total+1;
            total=((others+f[c])%MOD+MOD)%MOD;
        }
        return total;        
    }
};

参考链接：参考链接