题目分析

本题的方法容易想到，但是思路不容易想到。我开始做这个题目的时候，也做错了，在下面的分析中会说明错误的原因。

动态规划

本题使用动态规划，看到题目中答案要对10^9 + 7取余，再根据本题的性质，容易想到是动态规划的解法。

我当时错误的做法是，认为dp[i]表示以前i个字符结尾组成的非空子序列个数。则每一个都可以后面跟第i + 1个字符，且第i + 1个字符可以单独出现。所以有dp[i + 1] = dp[i] x 2 + 1。

上面做法的错误在于，dp[i]表示的前i个字符组成的非空子序列S1，可能与S2 + 第i + 1个字符重复。举个例子”aaa”，dp[2]表示的前2个字符组成的非空子序列中包括”a”，”aa”，此时”a”和第三个字符”a”组成的”aa”和前两个字符组成的”aa”重复。

正确的方案要注意下面两个要点：

假设第i个字符为s[i]，那么之前最后一个字符为’a’的子序列数，都可以加上s[i]组成一个新的子序列。
如果第m个字符为’a’，第n个字符也为’a’，且有m < n，那么以第n个字符结尾的子序列一定是包含以第m个字符结尾的子序列。这很好理解，直接将最后一位(第m位的’a’)换成第n位的’a’即可。

举个例子，’xxayya’中以第三位’a’结尾的子序列为”a”, “xa”, “xxa”，以第六位’a’结尾的子序列，一定是包含第三位’a’结尾的子序列，因为将’a’(第三位)换成’a’(第六位)即可。

综合上面两点，用dp[i]表示以第i位结尾可以组成的非空子序列个数。
$$ dp[i] = \sum_{c = a-z}^{alpha[c] \ge 0}{dp[alpha[c]]} + 1 $$

其中alpha[c]表示字符c出现最晚的索引位置。

因为字符只有26个，因此算法的**时间复杂度为O(n)，空间复杂度为O(n)**。

class Solution {
    public static final int MOD = 1000000007;

    public int distinctSubseqII(String s) {
        int n = s.length();
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int[] alpha = new int[26];
        Arrays.fill(alpha, -1);
        for (int i = 0; i < n; i++) {
            for (int c = 0; c < 26; c++) {
                if (alpha[c] != -1) {
                    dp[i] = (dp[i] + dp[alpha[c]]) % MOD;
                }
            }
            alpha[s.charAt(i) - 'a'] = i;
        }
        int res = 0;
        for (int i = 0; i < 26; i++) {
            if (alpha[i] != -1) {
                res = (res + dp[alpha[i]]) % MOD;
            }
        }
        return res;
    }
}

上述做法可以进行优化，我们只需要保留每个字符对应的子序列个数，因此空间复杂度可以优化到O(1)

class Solution {
    public static final int MOD = 1000000007;

    public int distinctSubseqII(String s) {
        int n = s.length();
        int[] alpha = new int[26];
        for (int i = 0; i < n; i++) {
            int cnt = 1;
            for (int c = 0; c < 26; c++) {
                cnt = (cnt + alpha[c]) % MOD;
            }
            alpha[s.charAt(i) - 'a'] = cnt;
        }
        int res = 0;
        for (int i = 0; i < 26; i++) {
            res = (res + alpha[i]) % MOD;
        }
        return res;
    }
}

刷题总结

其实本题不算是一个DP的困难题，DP有很多复杂的变种，只不过本题稍微绕了一点点弯，小伙伴们要多坚持刷题。