Leetcode 940. Distinct Subsequences II / 1987. Number of Unique Good Subsequences #240
Description
一、Distinct Subsequences II
虽然从时间复杂度和参数(仅有一个字符串)可以推测出要用动态规划，但实际上可以根据无后效性(后面作用于前)和有重复子问题，也可以推断出要用DP。
接下来关键是定义DP缓存和转移方程。假设dp[i]表示以i结尾的subsequences数目。然后考虑如何通过dpj求dp[i]：dp[i]相当于在dp[j]的subsequences上增加j字符，所以如果字符i不等于字符j，直接dp[i] += dp[j]；但实际上要考虑distinct，所以假设j字符等于i字符，也就是说i字符已经在前面出现过了，那么j之前所有的subsequences都不用看考虑了，因为dp[j]已经记录过了，所以最后我们只需要从j字符开始。
class Solution {
public int distinctSubseqII(String s) {
int n = s.length();
int[] dp = new int[n];
dp[0] = 1;
final int MOD = (int)(1e9) + 7;
int[] marks = new int[26];
Arrays.fill(marks, -1);
marks[s.charAt(0) - 'a'] = 0;
int res = 1;
for (int i = 1; i < n; i++) {
char c = s.charAt(i);
for (int j = (marks[c - 'a'] == -1 ? 0 : marks[c - 'a']); j < i; j++) {
dp[i] = (dp[i] + dp[j]) % MOD;
}
if (marks[c - 'a'] == -1) {
dp[i] = (dp[i] + 1) % MOD;
}
marks[c - 'a'] = i;
res = (res + dp[i]) % MOD;
}
return res;
}
}可以继续优化至O(n)，用前缀和数组sums记录前缀和。要注意爆栈的问题，用long存储，保证相加不会超模，然后相加后再取模，并且减法也要加上MOD再取模。
class Solution {
public int distinctSubseqII(String s) {
int n = s.length();
long[] dp = new long[n];
long[] sums = new long[n];
dp[0] = 1;
sums[0] = 1;
final int MOD = (int)(1e9) + 7;
int[] marks = new int[26];
Arrays.fill(marks, -1);
marks[s.charAt(0) - 'a'] = 0;
for (int i = 1; i < n; i++) {
char c = s.charAt(i);
if (marks[c - 'a'] != -1) {
dp[i] = (sums[i - 1] - (marks[c - 'a'] > 0 ? sums[marks[c - 'a'] - 1] : 0) + MOD) % MOD;
} else {
dp[i] = (sums[i - 1] + 1) % MOD;
}
marks[c - 'a'] = i;
sums[i] = (sums[i - 1] + dp[i]) % MOD;
}
return (int) sums[n - 1];
}
}第二种做法来自[Java/C++/Python] DP, 4 lines O(N) Time, O(1) Space。时间复杂度可以优化至O(n)。
考虑建立长度为26的ends数组，ends[i]代表以字符i+'a'结尾的subsequences个数。那么对于某个新字符c，要加上它，等于遍历所有字符结尾(遍历ends数组)，然后最后加上一(自己本身)。假如它本身在前面已经重复出现，那么之前的生成的subsequences也会重复出现。自身也有重复子问题。
我的方法是以j字符结尾，这里是以固定字符结尾，目的是将时间复杂度缩减至O(26n)，这是一种新思路。
class Solution {
public int distinctSubseqII(String s) {
long[] ends = new long[26];
final int MOD = (int) (1e9) + 7;
for (char c : s.toCharArray()) {
ends[c - 'a'] = Arrays.stream(ends).sum() % MOD + 1;
}
return (int) (Arrays.stream(ends).sum() % MOD);
}
}二、115. Distinct Subsequences
这题就更简单了。定义dp[i][j]表示0i子字符串s中等同于0j子字符串t的subsequences的个数。dp[i][i]是最终答案。转移方程是dp[i][j] = s.charAt(i) == t.charAt(j) ? dp[i - 1][j - 1] + dp[i - 1][j] : dp[i - 1][j]。
稍微注意的是我本想用dp[m+1][n+1]来初始化，但最终还是选择用dp[m][n]长度，要多一步初始化第一列和第一行。
class Solution {
public int numDistinct(String s, String t) {
int m = s.length(), n = t.length();
int[][] dp = new int[m][n];
// init
dp[0][0] = s.charAt(0) == t.charAt(0) ? 1 : 0;
for (int i = 1; i < m; i++) {
dp[i][0] = s.charAt(i) == t.charAt(0) ? dp[i - 1][0] + 1 : dp[i - 1][0];
}
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
if (s.charAt(i) == t.charAt(j)) {
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[m - 1][n - 1];
}
}我还尝试DFS+记忆化搜索来做。但TLE了，估计是选或不选这一步耗时太长了。
三、1987. Number of Unique Good Subsequences
1987. Number of Unique Good Subsequences
这题我一直没想出来。不知道如何利用无前缀0这一性质。
不妨从例子出发，然后先考虑O(n^2)，最后再优化至O(n)。考虑字符串"10110"，从左到右遍历结果分别是[1],[1,10,0],[1,10,0,11,101]...可以作图分析。
最难的是要发现字符串自己的自增性，比如101，要加'1'，那么对"10"加'1'就覆盖了"101"。像之前我的想法根据dp[j]和dp[i]不实用了，因为分不清0和1。不妨直接以0和1分类。
ends，ends1表示以0和1结尾的符合条件的子序列(单独0不计入)个数。假如是新的字符是1，则是ends0+ends1+1(本身)，否则是ends0+ends1。has0单独计算。
class Solution {
public int numberOfUniqueGoodSubsequences(String binary) {
int n = binary.length();
final int MOD = (int)(1e9) + 7;
int ends0 = 0, ends1 = 0, has0 = 0;
for (char c : binary.toCharArray()) {
if (c == '1') {
ends1 = (ends1 + ends0 + 1) % MOD;
} else {
ends0 = (ends0 + ends1) % MOD;
has0 = 1;
}
}
return (ends0 + ends1 + has0) % MOD;
}
}