题目
给定一个字符串 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"。
解题
方法一：动态规划
思路： 用一个数组存储26个字母结尾的字符串数量，每往后读一个就把整个数组全加起来再加一更新对应字母结尾的数组
而且这样做法，不会出现重复的问题
例子：
比如abcc
当i=0的时候，s[i]=‘a’，此时sum=1 ，有 a
当i=1的时候，s[i]=‘b’ , 此时sum=2，有 b，ab
当i=2的时候，s[i]=‘c’,此时sum=4，有c，ac，bc，abc （在上面两种情况下，末尾都补c，还有加上单独一个c的情况）
当i=3的时候，s[i]=‘c’,此时sum=8,有 c， ac ，bc，ab ，cc，acc，bcc，abcc
class Solution { public: const int MOD=1e9+7; int distinctSubseqII(string s) { vector<int> line(26); int n=s.size(); for(int i=0;i<n;i++){ int sum=0; for(int j=0;j<26;j++){ sum=(sum+line[j])%MOD; } line[s[i]-'a']=sum+1; } int res=0; for(int i=0;i<26;i++){ res=(res+line[i])%MOD; } return res; } };
