940. Distinct Subsequences II

https://leetcode.com/problems/distinct-subsequences-ii/

问字符串能组成多少个不同的subsequence。数数目而且是subsequence，DP。分成N步，第i步相当于把当前所有以不同字符结尾的每个子序列(以及空序列)加上S[i]形成新字符串，这些就是以S[i]结尾的所有子序列数目, 即end[i]_{i} = sum(end_{i-1}) + 1。这步新增加的为end[i]_{i}减去它的上一个值end[i]_{i - 1}，也就是added = sum(end_{i-1}) + 1 - end[i]_{i - 1}。最后返回所有字符结尾的子序列: sum(end_{N})。

答案参考自这。

/*
 * @lc app=leetcode id=940 lang=cpp
 *
 * [940] Distinct Subsequences II
 *
 * https://leetcode.com/problems/distinct-subsequences-ii/description/
 *
 * algorithms
 * Hard (40.31%)
 * Likes:    229
 * Dislikes: 11
 * Total Accepted:    7.2K
 * Total Submissions: 17.6K
 * Testcase Example:  '"abc"'
 *
 * 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
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 */

// @lc code=start
class Solution {
public:
    int distinctSubseqII(string S) {
        const int N = S.length(), M = 1e9 + 7;
        int res = 0; 
        vector<int> end(26, 0);
        for (const auto c : S) {
            int i = c - 'a';
            int added = (res - end[i] + 1) % M;
            res = (res + added) % M;
            end[i] = (end[i] + added) % M;
        }
        return (res + M) % M;
    }
};
// @lc code=end