⭐️940. 不同的子序列 II⭐️

🔐题目详情

940. 不同的子序列 II

难度困难

给定一个字符串 s，计算 s 的 不同非空子序列 的个数。因为结果可能很大，所以返回答案需要对 10^9 + 7 取余 。

字符串的 子序列 是经由原字符串删除一些（也可能不删除）字符但不改变剩余字符相对位置的一个新字符串。

• 例如，"ace" 是 "***a***b***c***d***e***" 的一个子序列，但 "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 仅由小写英文字母组成

💡解题思路

基本思路： 动态规划

解题思路：
状态定义： 为了方便，我们记字符串的下标从1数起，不妨定义 $f[i][j]$表示前 $i$个字符以字母表第 $j$个字母结尾时子序列的个数。

确定初始状态： 很显然，从前 $0$个字符选择， $f[0][j] = 0$。

状态转移方程： 不妨记字符串为 $s$，不失一般性地考虑，有两种情况，第一种那就是第 $i$个字符 $s[i - 1]$与第 $j$个字母不同时，即s[i - 1] - 'a' != j时：

$$f[i][j] = f[i - 1][j]$$

另外一种就是第 $i$个字符 $s[i-1]$与第 $j$个字母相同时，即s[i - 1] - 'a' == j时， $f[i][j]$等于第i-1状态所以子序列和再加上新增加 $s[i-1]$字符后的一种子序列：

$$f[i][j] = \sum_{j=0}^{25}f[i-1][j] + 1$$

最终字符串 $s$的总序列和即为n状态下所有子序列数量的和：

$$ans=\sum_{j=0}^{25}f[n][j]$$

优化：

我们发现地i行的状态均依赖于第i-1行，因此可以使用滚动数组优化空间，其实我们并没有必要去记录每一个 $f[i][j]$，我们可以直接记录总的子序列方案数ans，这样可以避免更新时重复对累加前面状态的子序列方案数。

🔑源代码

序列DP：

class Solution {
    private static final int MOD = (int) 1e9 + 7;
    public int distinctSubseqII(String s) {
        char[] cs = s.toCharArray();

        int n = cs.length;
        int[][] f = new int[n + 1][26];
        //确定初始状态f[0][j] = 0
        //状态转移

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < 26; j++) {
                if (cs[i - 1] - 'a' != j) {
                    f[i][j] = f[i - 1][j];
                } else {
                    int cur = 1;
                    for (int k = 0; k < 26; k++) {
                        cur = (cur + f[i - 1][k]) % MOD;
                    }
                    f[i][j] = cur;
                }
            }
        }
        int ans = 0;
        for (int j = 0; j < 26; j++) ans = (ans + f[n][j]) % MOD;
        return ans;
    }
}

使用动态和优化：

class Solution {
    private static final int MOD = (int) 1e9 + 7;
    public int distinctSubseqII(String s) {
        char[] cs = s.toCharArray();

        int n = cs.length;
        int ans = 0;
        int[] f = new int[26];

        //状态转移
        for (int i = 0; i < n; i++) {
            int ci = cs[i] - 'a';
            //记录上一个状态对应结尾字符为第ci个字母的子序列个数
            int prev = f[ci];
            //更新f[ci]
            f[ci] = (ans + 1) % MOD;
            //更新ans
            ans = (ans + f[ci]) % MOD;
            //因为ans取模后可能会比prev小，因此加上一个MOD，防止出现负数，反正在符号不改变的情况下加上一个MOD在去MOD的模结果不会改变
            ans = (ans - prev + MOD) % MOD;
        }
        return ans;
    }
}

🌱总结

本题为序列DP运用题，难点为状态转移的优化。