LeetCode 940. 不同的子序列 II（动态规划）

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

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

示例 3：
输入："aaa"
输出：3
解释：3 个不同的子序列分别是 "a", "aa" 以及 "aaa"。
 
提示：
S 只包含小写字母。
1 <= S.length <= 2000

class Solution {
public:
    int distinctSubseqII(string S) {
        int n = S.size(), mod = 1e9+7;
        vector<int> dp(n+1, 0);
        dp[0] = 1;//空字符串
        vector<int> prev(26, -1);
        // 之前最近的相同字符 pos
        for(int i = 0; i < n; i++) 
        {
            dp[i+1] = (dp[i]*2)%mod;
            // 当前字符跟之前的结合，不结合，产生的方案数
            if(prev[S[i]-'a'] != -1)
            // 之前有重复的 相同字符，会产生重复计数
                dp[i+1] = (dp[i+1]-dp[prev[S[i]-'a']]+mod)%mod;
            prev[S[i]-'a'] = i;//更新最近的字符位置
        }
        return dp[n]-1;
    }
};