## Algorithm

Problem Name: 1035. Uncrossed Lines

You are given two integer arrays `nums1` and `nums2`. We write the integers of `nums1` and `nums2` (in the order they are given) on two separate horizontal lines.

We may draw connecting lines: a straight line connecting two numbers `nums1[i]` and `nums2[j]` such that:

• `nums1[i] == nums2[j]`, and
• the line we draw does not intersect any other connecting (non-horizontal) line.

Note that a connecting line cannot intersect even at the endpoints (i.e., each number can only belong to one connecting line).

Return the maximum number of connecting lines we can draw in this way.

Example 1:

```Input: nums1 = [1,4,2], nums2 = [1,2,4]
Output: 2
Explanation: We can draw 2 uncrossed lines as in the diagram.
We cannot draw 3 uncrossed lines, because the line from nums1[1] = 4 to nums2[2] = 4 will intersect the line from nums1[2]=2 to nums2[1]=2.
```

Example 2:

```Input: nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
Output: 3
```

Example 3:

```Input: nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
Output: 2
```

Constraints:

• `1 <= nums1.length, nums2.length <= 500`
• `1 <= nums1[i], nums2[j] <= 2000`

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
Integer[][] dp;
public int maxUncrossedLines(int[] A, int[] B) {
dp = new Integer[A.length][B.length];
return helper(A, 0, B, 0);
}

private int helper(int[] A, int idxA, int[] B, int idxB) {
if (idxA == A.length || idxB == B.length) {
return 0;
}
if (dp[idxA][idxB] != null) {
return dp[idxA][idxB];
}
if (A[idxA] == B[idxB]) {
dp[idxA][idxB] = 1 + helper(A, idxA + 1, B, idxB + 1);
}
else {
dp[idxA][idxB] = Math.max(helper(A, idxA + 1, B, idxB), helper(A, idxA, B, idxB + 1));
}
return dp[idxA][idxB];
}
}
``````
Copy The Code &

Input

cmd
nums1 = [1,4,2], nums2 = [1,2,4]

Output

cmd
2

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const maxUncrossedLines = function(A, B) {
const lenA = A.length
const lenB = B.length
const dp = Array.from({length: lenA + 1}, () => new Array(lenB + 1).fill(0))
for(let i = 1; i  < = lenA; i++) {
for(let j = 1; j  < = lenB; j++) {
if(A[i - 1] === B[j - 1]) {
dp[i][j] = 1 + dp[i - 1][j - 1]
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])
}
}
}
return dp[lenA][lenB]
};
``````
Copy The Code &

Input

cmd
nums1 = [1,4,2], nums2 = [1,2,4]

Output

cmd
2

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
dp, m, n = collections.defaultdict(int), len(A), len(B)
for i in range(m):
for j in range(n):
dp[i, j] = max(dp[i - 1, j - 1] + (A[i] == B[j]), dp[i - 1, j], dp[i, j - 1])
return dp[m - 1, n - 1]
``````
Copy The Code &

Input

cmd
nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]

Output

cmd
3

### #4 Code Example with C# Programming

```Code - C# Programming```

``````
using System;

namespace LeetCode
{
public class _1035_UncrossedLines
{
public int MaxUncrossedLines(int[] A, int[] B)
{
var rows = A.Length;
var cols = B.Length;
var dp = new int[rows + 1, cols + 1];

for (int i = 1; i  < = rows; i++)
for (int j = 1; j  < = cols; j++)
{
if (A[i - 1] == B[j - 1])
dp[i, j] = dp[i - 1, j - 1] + 1;
else
dp[i, j] = Math.Max(dp[i - 1, j], dp[i, j - 1]);
}

return dp[rows, cols];
}
}
}
``````
Copy The Code &

Input

cmd
nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]

Output

cmd
3