【LeetCode】不同的子序列 II [H]（动态规划）

940. 不同的子序列 II - 力扣（LeetCode）

一、题目

给定一个字符串 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"。

提示：

• 1 <= s.length <= 2000
• s 仅由小写英文字母组成

二、代码

class Solution {
    public int distinctSubseqII(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
 
        // 求余数
        int mod = 1000000007;
        char[] s = str.toCharArray();
        // all是当前所有的子集数量（去重后的数量）
        // 需要将all初始化为1，否则整个流程无法推进下去
        int all = 1;
        // 记录当前以index+'a'字符结尾的子序列有多少个
        int[] count = new int[26];
        // 从左向右
        for (int i = 0; i < s.length; i++) {
            // 当前遍历到的字符
            int index = s[i] - 'a';
            // 加上这个字符一共会增加的子集数量，剔除掉之前已经重复出现的子集
            // 如果不算重复的话，本轮一共新增的子集数量就是all个，因为是在之前all个子集的基础上，在他们的后面追加一个s[i]，自然新增加的子集数量就是all个
            // 但是有可能新增的在之前已经存在了，这就出现重复了，需要去重
            // 这一轮重复出现的子集，在之前中为什么会出现呢，一定是因为之前遍历到的字符追加到之前的子集后面来构造出来的，也就一共构造出来count[index]个，而这一轮又遍历到了s[i]，因为之前构造出来的所有子集都会保留，所以这一轮一定也会再次重复构造出来count[index]个相同的以s[i]结尾的子集，所以这里我们就减掉count[index]就可以了
            // 这里注意要加m，然后再%m。因为curAll和map.get(x)都是被模处理过的，他们两个相减有可能是负数，所以要先加一个m保证不是负数，然后再模m，并不影响正确结果
            int add =  (all - count[index] + mod) % mod;
            // 计算本轮新的all，以前的all加上去重后的新增数量
            all = (all + add) % mod;
            // 以s[i]结尾的子集增加了all（已去重），累加到count数组中
            count[index] = (count[index] + add) % mod;
        }
        // 不算空集，要减去1
        // 上述的所有过程中都要跟着取模操作，这是题目要求，为了避免数据溢出
        return (all - 1 + mod) % mod;
    }
}

三、解题思路 

这道题需要注意的点就是在增加新的子序列的时候，有可能新增的子序列是在以前出现过的，需要做去重处理。我们从左向右遍历，每一次就把遍历到的字符追加到已存在的子序列集合的尾部，然后再去做一次去重操作，当整个字符串遍历完之后，就能求出总的子序列数量。