940. 不同的子序列 II
Desciption
给定一个字符串 S，计算 S 的不同非空子序列的个数。
因为结果可能很大，所以返回答案模 10^9 + 7.
S 只包含小写字母。
1 <= S.length <= 2000
示例：
输入："aba"
输出：6
解释：6 个不同的子序列分别是 "a", "b", "ab", "ba", "aa" 以及 "aba"。
Solution
这种计算数量的题目，可以考虑dp。
用 dp[i] 表示前 i 个字符的非空子序列的数量，一个比较简单的转移方程是 dp[i] = dp[i-1] * 2，2 表示选和不选第 i 个字符加入子序列的场景。
但是这样会有两个问题：
- 会包含空子序列
- 会重复计算部分子序列
对于第一个问题：思考一下，重新定义 dp 数组，dp[i] 表示前 i 个字符的子序列数量（包含空子序列），最后只需要将结果减 1，就是非空子序列的数量。
对于第二个问题：
对于 “abc” 这个字符串，dp[i] = dp[i-1] * 2，最后结果减 1，答案是 7，是正确的
对于 “abab” 这个字符串，正确的答案是11，用我们的状态转移方程，最后结果减 1，答案是 15
我们将状态转移画出来，看看重复计算了哪些子序列：
dp[0] = 2，它包括 ("", “a”)；
dp[1] = 4，它包括 ("", “a”, “b”, “ab”)；
dp[2] = 8，它包括 ("", “a”, “b”, “ab”, “aa”, “ab”, “ba”, “aba”)；
dp[3] = 16，它包括 ("", “a”, “b”, “ab”, aa", “ab”, “ba”, “aba”, “b”, “ab”, “bb”, “abb”, “aab”,“abb”,“bab”,“abab”)
再看看正确的状态是怎么样：
- dp[0] = 2，它包括 ("", “a”)；
- dp[1] = 4，它包括 ("", “a”, “b”, “ab”)；
- dp[2] = 7，它包括 ("", “a”, “b”, “aa”, “ab”, “ba”, “aba”)；
- dp[3] = 12，它包括 ("", “a”, “b”, “aa”, “ab”, “ba”, “bb”, “aab”, “aba”, “abb”, “bab”, “abab”)
我们再思考一下状态怎么转移？从 dp[2] 到 dp[3]，我们只会在 dp[2] 中的 (“b”, “aa”, “ab”, “ba”, “aba”) 的末尾增加 b，而忽略掉 ("", “a”)，因为它们会得到重复的子序列。我们可以发现，这里的 ("", “a”) 刚好就是 dp[0]，也就是上一次增加 b 之前的子序列集合。因此我们就得到了如下的状态转移方程：
dp[k] = 2 * dp[k - 1] - dp[last[S[k]] - 1]
即在计算 dp[k] 时，首先会将 dp[k - 1] 对应的子序列的末尾添加 S[k] 得到额外的 dp[k - 1] 个子序列，并减去重复出现的子序列数目，这个数目即为上一次添加 S[k] 之前的子序列数目 dp[last[S[k]] - 1]
Code
public int distinctSubseqII(String s) {
int n = s.length();
int mod = 1000000007;
int[] dp = new int[n + 1];
int[] last = new int[26];
Arrays.fill(dp, 0);
Arrays.fill(last, -1);
dp[0] = 1;
for (int i = 1; i <= n; ++i) {
dp[i] = dp[i - 1] * 2 % mod;
int x = s.charAt(i - 1) - 'a';
if (last[x] >= 0) {
dp[i] = (dp[i] + mod - dp[last[x]]) % mod;
}
last[x] = i - 1;
}
dp[n] = (dp[n] + mod - 1) % mod;
return dp[n];
}