剑指 Offer II 097. 子序列的数目
给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，“ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是）
题目数据保证答案符合 32 位带符号整数范围。
示例 1：
输入：s = “rabbbit”, t = “rabbit”
输出：3
解释：
如下图所示, 有 3 种可以从 s 中得到 “rabbit” 的方案。
rabbbit
rabbbit
rabbbit
示例 2：
输入：s = “babgbag”, t = “bag”
输出：5
解释：
如下图所示, 有 5 种可以从 s 中得到 “bag” 的方案。
babgbag
babgbag
babgbag
babgbag
babgbag
提示：
0 <= s.length, t.length <= 1000
s 和 t 由英文字母组成
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/21dk04
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
分析
方法一：空间复杂度O(mn)
1、找状态转移方程。设f(i, j)表示字符串s的索引0到 i 的子字符串中出现字符串t的索引0到 j 的子字符串的个数，对于f(i, j)，对s(i)与t(j)进行比较，有两种情况：s(i)和t(j)匹配，或者不匹配；
如果匹配，f(i, j) = f(i – 1, j – 1) + f(i – 1, j)，意为：f(i, j)是下面两者的和：① s 的索引0到 i – 1 的子字符串中出现t的索引0到 j – 1 的子字符串的个数，可理解为：s(i)和t(j)匹配的时候，f(i – 1, j – 1)匹配的字符串后面连接字符t(j)形成新的字符串，子序列发数量还是f(i – 1, j – 1) ② s 的索引0到 i – 1 的子字符串中出现t的索引0到 j 的子字符串的个数，可理解为：先不考虑s(i)和t(j)的匹配，s 的索引0到 i – 1 的子字符串中出现t的索引0到 j 的子字符串的个数也应该算入f(i, j)的总数。这两者之和组成f(i, j)的充要条件的原因是：
s 的索引0到 i 的子字符串中出现t的索引0到 j 的子字符串的个数 =
只考虑以s(i)与t(j)匹配的字符s(i)为结尾子序列个数，即s 的索引0到 i – 1 的子字符串中出现t的索引0到 j – 1 的子字符串的个数
∪
除了以s(i)为结尾的子字符串中出现t的索引0到 j 的子字符串的子序列个数即 s 的索引0到 i – 1 的子字符串中出现t的索引0到 j 的子字符串的个数
这个充要条件需要多加理解。s(i)和t(j)不匹配的时候就比较容易理解了，f(i, j) = f(i – 1, j)， s 的索引0到 i 的子字符串中出现t的索引0到 j 的子字符串的个数跟 s 的索引0到 i – 1 的子字符串中出现t的索引0到 j 的子字符串的个数。
另外考虑 i 和 j 等于0的情况，i 如果是0表示s用来匹配的是个空字符串，所以f(0, j) = 0 (j != 0)，如果 i j 同时为0，那么表示以空串匹配 f(0, 0) = 1，如果 j = 0，f(i, 0) = 1，表示只有空串进行匹配且一定可以匹配空串。
2、根据状态转移方程写dp数组。状态转移方程比较简单，先把第一行第一列填好，按照以上分析对dp数组其他部分进行补充即可。
方法二：空间复杂度O(n)
按照之前做的题的规律，二维的dp数组一般都可以进行优化，根据方法一中的分析，f(i, j)只用到了f(i – 1, j – 1)和f(i – 1, j)，我们可以降维成1维，因为每次计算只用到（或者改变）了两层的值，对第一层的值进行保存再对下一层进行操作即可，下面的题解中没有用到变量保存改变前的值，因为是利用倒序遍历，先改变（或添加）的是后面的值，后面的值必要进行保存，所以没有必要用变量进行记录。
题解（Java）
方法一：空间复杂度O(mn)
class Solution {
public int numDistinct(String s, String t) {
int[][] dp = new int[s.length() + 1][t.length() + 1];
dp[0][0] = 1;
for (int i = 0; i < s.length(); i++) {
dp[i + 1][0] = 1;
for (int j = 0; j <= i && j < t.length(); j++) {
dp[i + 1][j + 1] = s.charAt(i) == t.charAt(j) ? dp[i][j] + dp[i][j + 1] : dp[i][j + 1];
}
}
return dp[s.length()][t.length()];
}
}
方法二：空间复杂度O(n)
class Solution {
public int numDistinct(String s, String t) {
int[] dp = new int[t.length() + 1];
if (s.length() > 0) {
dp[0] = 1;
}
for (int i = 0; i < s.length(); i++) {
for (int j = Math.min(i, t.length() - 1); j >= 0; j--) {
if (s.charAt(i) == t.charAt(j)) {
dp[j + 1] += dp[j];
}
}
}
return dp[t.length()];
}
}