1
class Solution {
2
 public:
3
  int maxUncrossedLines(vector<int> &nums1, vector<int> &nums2) {
4
    int m = nums1.size(), n = nums2.size();
5
    if (m < n) {
6
      swap(nums1, nums2);
7
      swap(m, n);
8
    }
9
    vector<int> dp(n + 1);
10
    for (int i = 1; i <= m; i++) {
11
      int prev = 0;
12
      for (int j = 1; j <= n; j++) {
13
        int curr = dp[j];
14
        if (nums1[i - 1] == nums2[j - 1]) {
15
          dp[j] = prev + 1;
16
        } else {
17
          dp[j] = max(dp[j - 1], curr);
18
        }
19
        prev = curr;
20
      }
21
    }
22
    return dp[n];
23
  }
24
};