解题思路：
- 本题为动态规划思想
- 基本思想：
- 以结尾的字母来划分集合，避免重复的子序列。 遍历字符串，更新以当前字符串结尾的子序列数量为：以26个字母为结尾的子序列的数量（就是把当前字符串加到所有子序列的前面） + 1（自身）。 遍历结束以后，以每种字符结束的子序列数量都已经计算好了。
- 例子：
- 以 abcac 为例，首先以第一个 a 为结尾的子字符串只有他自己 {a} 故此时的dp['a'-'a']=1;
- 以此类推，以 b 为结尾的字符串集为 {ab,b} ，故此时的dp['a'-'a']=2;以第一个 c 为结尾的字符集为 {ac,abc,bc,c} ;以第二个 a 为结尾的字符集为 {aa,aba,ba,aca,abca,bca,ca,a} ;
归约：
- dp 长度为26，每一个位置存储一个以其字母为结尾的子字符串个数
错误代码分析：
class Solution {
public:
int dp[26];
int distinctSubseqII(string s) {
int n=s.length();
long long mod=pow(10,9)+7;
for(int i=0;i<n;i++)
{
dp[s[i]-'a']+=accumulate(dp,dp+26,1ll)%mod; //错误的位置在这里
}
return accumulate(dp,dp+26,0ll)%mod;
}
};
错误原因是 ‘+’ ，不应该使用 ‘+’ ，由于结尾相同的话，直接更新就行，不用将之前的字符串相加，因为之前找到的会在后面继续找到，被包含了
正确代码：
class Solution {
public:
int dp[26];
int distinctSubseqII(string s) {
int n=s.length();
long long mod=pow(10,9)+7;
for(int i=0;i<n;i++)
{
dp[s[i]-'a']=accumulate(dp,dp+26,1ll)%mod;
}
return accumulate(dp,dp+26,1ll)%mod;
}
};
复杂度分析：
- 时间复杂度为O(n);
- 空间复杂度为O(1);