题目描述
leetcode 困难题
给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，”ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是）
题目数据保证答案符合 32 位带符号整数范围。
示例1：
1
2
3
4
5
6
7
| 输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下图所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit
|
提示1：
1
2
| 0 <= s.length, t.length <= 1000
s 和 t 由英文字母组成
|
动态规划
定义 $dp[i][j]$ 表示子串 $s[0…i]$ 中子序列 $t[0…j]$ 出现的个数。
令 $dp$ 从 $0$ 开始，表示空串。并且当 $j = 0$ 时，$dp[i][0]$ 为 $1$ ，因为空字符串是任何字符串的子序列。其他情况下：
$$
\begin{align}
&dp(i, j) = dp(i - 1, j) s[i - 1] \ne t[j - 1] \\
&dp(i, j) = dp(i - 1, j) + dp(i - 1, j - 1) s[i - 1] = t[j - 1] \\
\end{align}
$$
$dp[n][m]$ 为答案，$n$ 和 $m$ 分别为两个字符串的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int numDistinct(String s, String t) {
int n = s.length();
int m = t.length();
int[][] dp = new int[n + 1][m + 1];
for(int i = 0; i < n; i++){
dp[i][0] = 1;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
dp[i][j] = dp[i - 1][j];
if(s.charAt(i - 1) == t.charAt(j - 1)){
dp[i][j] += dp[i - 1][j - 1];
}
}
}
return dp[n][m];
}
}
|
滚动数组
每一层只依赖上一层的结果，逆序遍历即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int numDistinct(String s, String t) {
int n = s.length();
int m = t.length();
int[] dp = new int[m + 1];
dp[0] = 1;
for(int i = 1; i <= n; i++){
for(int j = m; j >= 1; j--){
if(s.charAt(i - 1) == t.charAt(j - 1)){
dp[j] += dp[j - 1];
}
}
}
return dp[m];
}
}
|