115. 不同的子序列
给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。
题目数据保证答案符合 32 位带符号整数范围
示例 1：
输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
[rabb]b[it]
[rab]b[bit]
[ra]b[bbit]
示例 2：
输入：s = "babgbag", t = "bag"
输出：5
解释：
如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。
[b]abgb[ag]
ba[b]gb[ag]
babg[bag]
[ba]bgba[g]
[ba]b[g]bag
提示：
1 <= s.length, t.length <= 1000s和t由英文字母组成
解法
1. 递归
1. 思路
以 s 为 babgbag，t 为 bag 为例：
如果末尾字符不同，那么 s 需要左移直到找到相等的位置。
如果末尾字符相同，即 s[s.len - 1] == t[t.len - 1]，于是 s 有两种选择：
- 全部左移一位，开始判断两者的排除最后一个元素后的情况，即
s[s.len - 2]和t[t.len - 2]的情况。 - 由于 s 中其他位置也有可能存在与
t[t.len - 1]匹配的字符，所以，继续判断s[s.len - 2]和t[t.len - 1]的情况。
2. 代码
所以对应递归代码为：
class Solution {
public int numDistinct(String s, String t) {
return search(s, t, s.length() - 1, t.length() - 1);
}
/**
* p 为指向 s 中字符的指针，q 为指向 t 中字符的指针
*/
public int search(String s, String t, int p, int q) {
if (q < 0) {
return 1;
}
if (p < 0) {
return 0;
}
int count = 0;
while (p >= 0 && q >= 0) {
if (s.charAt(p) == t.charAt(q)) {
count += search(s, t, p - 1, q - 1);
}
// p 指针左移寻找下一个匹配的位置
p--;
}
return count;
}
}
3. 递归优化
如上写法只能通过部分用例，字符串比较长的用例会出现超时，即使加上记忆化搜索也不行。究其原因是因为除了递归中浪费的时间，p 进行左移遍历也会耗费时间，尤其是每一个递归层级中 p 指针都需要一直遍历到最左边，所有递归层级累加起来也会变得很耗时。所以可以通过记忆化搜索直接省略左移的过程，代码如下：
class Solution {
Map<String, Integer> map = new HashMap<>();
public int numDistinct(String s, String t) {
return search(s, t, s.length() - 1, t.length() - 1);
}
/**
* p 为指向 s 中字符的指针，q 为指向 t 中字符的指针
*/
public int search(String s, String t, int p, int q) {
if (q < 0) {
return 1;
}
if (p < 0) {
return 0;
}
// 记忆化搜索
String key = p + "-" + q;
if (map.containsKey(key)) {
return map.get(key);
}
int count = 0;
if (s.charAt(p) == t.charAt(q)) {
count = search(s, t, p - 1, q - 1) + search(s, t, p - 1, q);
} else {
count = search(s, t, p - 1, q);
}
map.put(key, count);
return count;
}
}
使用如上方法是可以 AC 的。
2. 动态规划
有了上面递归方法的铺垫，对应的动态规划思路也是一样的。
1. DP 数组定义
设 dp[i][j] 为以 s[i]、t[j]结尾时子序列的数量。
2. 状态转移方程
依据上面递归的思路：
如果：s[i - 1] == t[j - 1] 则 dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
如果：s[i - 1] != t[j - 1] 则 dp[i][j] = dp[i - 1][j]
3. DP 数组初始化
为了使二维 DP 数组初始化方便一般都需要多扩充一行和一列以表示，相当于加了个 null 值得情况。
由状态转移方程可知，数组不能全部初始化为 0，而 dp[i][j] 只与其上面和左上两个值有关。以 s 为 babgbag，t 为 bag 为例：
先忽略扩充的 null 值列。
第一行表示 s 为 b，t 分别为 b、ba 和 bag，以子序列数量来看只有 t 表示 b 的时候 dp[0][0] = 1，其余 dp[i][j] = 0，即使后面再出现 b 也还是 0。
第一列表示 s 为 b、ba、bab、babg、babgb、babgba、babgbag，t 为 b，s 中每出现一次 b，dp[i][j] 就应该 +1，依据状态转移方程 dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]，如果初始化扩充列的时候直接为 0，那么 dp[i][j] 就不会递增，所以需要将扩充的第一列初始化为 1。
依据扩充的第一列的情况，扩充的第一行需要初始化为 0。
4. 代码
class Solution {
public int numDistinct(String s, String t) {
int len1 = s.length();
int len2 = t.length();
int[][] dp = new int[len1 + 1][len2 + 1];
// 初始化第一列为 1
for (int i = 0; i <= len1; i++) {
dp[i][0] = 1;
}
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (s.charAt(i - 1) == t.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[len1][len2];
}
}
5. DP 数组压缩
由于 dp[i][j] 只与其上面和左上两个值有关，所以内层循环倒序遍历即可。正序遍历也可以，需要多维护下 dp[i - 1][j - 1]。
class Solution {
public int numDistinct(String s, String t) {
int len1 = s.length();
int len2 = t.length();
int[] dp = new int[len2 + 1];
// 初始化
dp[0] = 1;
for (int i = 1; i <= len1; i++) {
for (int j = len2; j > 0; j--) {
if (s.charAt(i - 1) == t.charAt(j - 1)) {
dp[j] = dp[j] + dp[j - 1];
} else {
dp[j] = dp[j];
}
}
return dp[len2];
}
}