# 1035. Uncrossed Lines

• Time: $O(mn)$
• Space: $O(mn)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public: int maxUncrossedLines(vector& nums1, vector& nums2) { const int m = nums1.size(); const int n = nums2.size(); vector> dp(m + 1, vector(n + 1)); for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j) dp[i][j] = nums1[i - 1] == nums2[j - 1] ? dp[i - 1][j - 1] + 1 : max(dp[i - 1][j], dp[i][j - 1]); return dp[m][n]; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution { public int maxUncrossedLines(int[] nums1, int[] nums2) { final int m = nums1.length; final int n = nums2.length; int[][] dp = new int[m + 1][n + 1]; for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j) dp[i][j] = nums1[i - 1] == nums2[j - 1] ? dp[i - 1][j - 1] + 1 : Math.max(dp[i - 1][j], dp[i][j - 1]); return dp[m][n]; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution: def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int: m = len(nums1) n = len(nums2) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): dp[i][j] = dp[i - 1][j - 1] + 1 \ if nums1[i - 1] == nums2[j - 1] \ else max(dp[i - 1][j], dp[i][j - 1]) return dp[m][n]