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];
}