# 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 仅由小写英文字母组成

# 题解

这题用到了动态规划，我们可以用一个长度为 26 的数组存储每一个字母位于末位时含有的不重复子序列个数，最初我们将其初始化为 0，对于第 i 位的字母，以它为最后一位的子序列数就是其前缀的不重复子序列数量 + 1 个，而这其中重复的子序列个数，就是我们存储的这个字母前一次为子序列最后一位时不重复子序列的个数。

class Solution {
public:
    int distinctSubseqII(string s) {
        vector<int> g(26,0);
        int ans=0;
        for(int i=0;i<s.length();i++){
            int m=s[i]-'a';
            int n=g[m];
            g[m]=ans+1;
            ans=((ans+g[m]-n)%(int)(1e9+7)+(int)(1e9+7))%(int)(1e9+7);
        }
        return ans;
    }
};