Given a string?S, count the number of distinct, non-empty subsequences of?S?.
Since the result may be large,?return the answer modulo?10^9 + 7.
Example 1:
Input: "abc"
Output: 7
Explanation: The 7 distinct subsequences are "a", "b", "c", "ab", "ac", "bc", and "abc".
Example 2:
Input: "aba"
Output: 6 Explanation: The 6 distinct subsequences are "a", "b", "ab", "ba", "aa" and "aba".
Example 3:
Input: "aaa"
Output: 3 Explanation: The 3 distinct subsequences are "a", "aa" and "aaa".
Note:
S?contains only lowercase letters.1 <= S.length <= 2000
这道题是之前那道 [Distinct Subsequences](http://www.cnblogs.com/grandyang/p/4294105.html) 的类似题目，这里只有一个字符串，让找出所有不同的子序列，如果字符串中没有重复字符，可以直接得到子序列的个数，但是这里由于重复字符的存在，就大大增加了难度。由于题目中提示了结果可能非常大，要对一个超大数取余，就相当于明确说了要用动态规划 Dynamic Programming 来做，下面就要来考虑 dp 数组的定义和状态转移方程的推导了。刚开始博主也是考虑用一个一维数组 dp，其中 dp[i] 表示以 S[i] 结尾的不同子序列的个数，就像 [这个帖子](https://leetcode.com/problems/distinct-subsequences-ii/discuss/192030/Java-DP-O\(N2\)-time-greater-O\(N\)-time-greater-O\(1\)-space) 中定义的一样，但是状态转移方程不好推导，那个帖子虽然代码可以跑通，但是解释的却不通，博主也纳闷这算是歪打正着么，希望哪位大神来解释一下。这里还是根据 [lee215 大神的帖子](https://leetcode.com/problems/distinct-subsequences-ii/discuss/192017/C%2B%2BJavaPython-4-lines-O\(N\)-Time-O\(1\)-Space) 来讲解吧。这里使用一个大小为 26 的一维数组 dp，其中 dp[i] 表示以字符 i+‘a‘ 结尾的不同子序列的个数，因为题目中限定了只有小写字母，所以只有 26 个。以 aba 这个例子来分析一下，当遇到开头的a时，那么以a结尾的子序列只有一个，就是a，当遇到中间的b时，此时知道以b结尾的子序列有2个，分别是 b 和 ab，是怎么得来的呢，其实是空串和a后面分别加个b得来的，此时貌似得到的值和通过 sum(dp)+1 计算的结果相等，再来验证一下这个成不成立。当遇到末尾的a的时候，那么此时以a结尾的子序列就有4个，分别是 a，aa，ba，aba，是怎么得来的？在这个a加入之前，当前所有的子序列有，a，b，ab，如果再算上一个空串，[]，a，b，ab，则在其后面各加上一个b，就可以得到结果了，貌似也符合 sum(dp)+1 的规律，这其实也并不难理解，因为在当前不同序列的基础上，加上任何一个字符都会得到另一个不同的子序列，后面的加1是为了加上空串的情况，这个就是状态转移方程了，最终的结果是把 dp 数组累加起来取余后返回即可，参见代码如下：
class Solution {
public:
int distinctSubseqII(string S) {
int M = 1e9 + 7;
vector<int> dp(26);
for (char c : S) {
dp[c - ‘a‘] = accumulate(dp.begin(), dp.end(), 1L) % M;
}
return accumulate(dp.begin(), dp.end(), 0L) % M;
}
};
Github 同步地址:
https://github.com/grandyang/leetcode/issues/940
类似题目：
Distinct Subsequences
参考资料：
https://leetcode.com/problems/distinct-subsequences-ii/
https://leetcode.com/problems/distinct-subsequences-ii/discuss/192017/C%2B%2BJavaPython-4-lines-O(N)-Time-O(1)-Space
https://leetcode.com/problems/distinct-subsequences-ii/discuss/192030/Java-DP-O(N2)-time-greater-O(N)-time-greater-O(1)-space
[LeetCode All in One 题目讲解汇总(持续更新中...)](https://www.cnblogs.com/grandyang/p/4606334.html)[LeetCode] 940. Distinct Subsequences II 不同的子序列之二
原文：https://www.cnblogs.com/grandyang/p/12735600.html
