dp[i][j] 表示在 s[i:] 的子序列中 t[j:] 出现的个数
s[i:] 表示 s 从下标 i 到末尾的子字符串，t[j:] 表示 t 从下标 j 到末尾的子字符串
边界：dp[i][n]=1
d[m][j] = 0, 0≤j<n
寻找转移方程：（从右到左）
a = dp[i][j]=dp[i+1][j+1]+dp[i+1][j] m[i] == n[j]
b = dp[i][j]=dp[i+1][j] m[i] != n[j]
class Solution {
public int numDistinct(String s, String t) {
int m = s.length(), n = t.length();
if (m < n) {
return 0;
}
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
dp[i][n] = 1;
}
for (int i = m - 1; i >= 0; i--) {
char sChar = s.charAt(i);
for (int j = n - 1; j >= 0; j--) {
char tChar = t.charAt(j);
if (sChar == tChar) {
dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j];
} else {
dp[i][j] = dp[i + 1][j];
}
}
}
return dp[0][0];
}
}
时间复杂度：O(mn)，其中 m 和 n 分别是字符串 s 和 t 的长度。二维数组 dp 有 m+1 行和 n+1 列，需要对 dp 中的每个元素进行计算。
空间复杂度：O(mn)，其中 m 和 n 分别是字符串 s 和 t 的长度。创建了 m+1 行 n+1 列的二维数组 dp。
image.png
dp[i][j]代表T前i字符串可以由S前j字符串组成最多个数.
所以动态方程:
当 S[j] == T[i], dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
当S[j] != T[i], dp[i][j] = dp[i][j-1]
image.png
dp[i][j] 为字符串s前i个字符中的字符串t的前j个字符的子序列个数
边界： d[i][0] = 1 空串是任意字符串的子序列
寻找转移方程：(从左到右)
a = dp[i-1][j-1]
b = dp[i-1][j]
m[i] == n[j] ，令m[i]和n[j]匹配，则dp[i-1][j-1]；令m[i]和n[j]不匹配，则dp[i-1][j]
m[i] ！= n[j] ，m[i]和n[j]不能匹配，则dp[i-1][j]
dp[i][j] = a + b = dp[i-1][j-1] + dp[i-1][j]
比葫芦画瓢，还行
class Solution {
public int numDistinct(String s, String t) {
1.定义d[i][j]
int[][] dp = new int[s.length() + 1][t.length() + 1];
2. 初始化
for (int i = 0; i < s.length() + 1; i++)
dp[i][0] = 1;
3.状态转移方程
for (int i = 1; i < s.length() + 1; i++) {
for (int j = 1; j < t.length() + 1; 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[s.length()][t.length()];
}
}
下面i,j 颠倒了，j是s的长度，i是t的长度
class Solution {
public int numDistinct(String s, String t) {
int[][] dp = new int[t.length() + 1][s.length() + 1];
for (int j = 0; j < s.length() + 1; j++) dp[0][j] = 1;
for (int i = 1; i < t.length() + 1; i++) {
for (int j = 1; j < s.length() + 1; j++) {
if (t.charAt(i - 1) == s.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];
else dp[i][j] = dp[i][j - 1];
}
}
return dp[t.length()][s.length()];
}
}
