Skip to main content

rustgym/leetcode/
_1035_uncrossed_lines.rs

1struct Solution;
2
3impl Solution {
4    fn max_uncrossed_lines(a: Vec<i32>, b: Vec<i32>) -> i32 {
5        let n = a.len();
6        let m = b.len();
7        let mut dp = vec![vec![0; m + 1]; n + 1];
8        for i in 0..n {
9            for j in 0..m {
10                if a[i] == b[j] {
11                    dp[i + 1][j + 1] = dp[i][j] + 1;
12                } else {
13                    dp[i + 1][j + 1] = dp[i][j + 1].max(dp[i + 1][j]);
14                }
15            }
16        }
17        dp[n][m]
18    }
19}
20
21#[test]
22fn test() {
23    let a = vec![1, 4, 2];
24    let b = vec![1, 2, 4];
25    let res = 2;
26    assert_eq!(Solution::max_uncrossed_lines(a, b), res);
27    let a = vec![2, 5, 1, 2, 5];
28    let b = vec![10, 5, 2, 1, 5, 2];
29    let res = 3;
30    assert_eq!(Solution::max_uncrossed_lines(a, b), res);
31    let a = vec![1, 3, 7, 1, 7, 5];
32    let b = vec![1, 9, 2, 5, 1];
33    let res = 2;
34    assert_eq!(Solution::max_uncrossed_lines(a, b), res);
35}