1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| struct Solution;
// @lc code=start
impl Solution {
/// ## 解题思路
/// - 动态规划
/// 1. 设 dp[i][j]: 表示s[..i], t[..j]的不同子序列个数;
/// 2. 目标: dp[s.len()][t.len()];
/// 3. 递推关系:
/// dp[i+1][j+1] = dp[i][j+1] (s[i] != t[j], s[i]和t[j]不同子序列数等同于s[(i-1)]和t[j])
/// = dp[i][j+1] + dp[i][j] (s[i] == t[j], 此时将匹配情况分2类:
/// a. 匹配子序列包含s[i]的, 个数有dp[i][j];
/// b. 匹配子序列不包含s[i]的, 个数为dp[i][j+1];
/// )
/// 4. 初始条件:
/// dp[i][0] = 1, (t为空, s中和t匹配的子序列为1)
pub fn num_distinct0(s: String, t: String) -> i32 {
let (s, t) = (s.as_bytes(), t.as_bytes());
let (m, n) = (s.len(), t.len());
let mut dp = vec![vec![0; n + 1]; m + 1];
for i in 0..m {
dp[i][0] = 1;
for j in 0..n {
dp[i + 1][j + 1] = if s[i] == t[j] {
dp[i][j + 1] + dp[i][j]
} else {
dp[i][j + 1]
};
}
}
dp[m][n]
}
/// - 优化:
/// dp[i+1][] 只和dp[i][]有关系, 用一维数组代替二维数组
pub fn num_distinct(s: String, t: String) -> i32 {
let (s, t) = (s.as_bytes(), t.as_bytes());
let (m, n) = (s.len(), t.len());
let mut dp = vec![0; n + 1];
dp[0] = 1;
for i in 0..m {
for j in (0..n).rev() {
if s[i] == t[j] {
dp[j + 1] += dp[j];
}
}
}
dp[n]
}
}
// @lc code=end
|