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.

&nbsp;
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


&nbsp;
Constraints:


	1 &lt;= nums1.length, nums2.length &lt;= 500
	1 &lt;= nums1[i], nums2[j] &lt;= 2000


class Solution:
    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
        
        @lru_cache(None)
        def dp(a,b):
            if a>=len(nums1) or b>=len(nums2): return 0
            if nums1[a]==nums2[b]: return 1+dp(a+1,b+1)
            else: return max(dp(a+1,b),dp(a,b+1))
        
        return dp(0,0)
class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int m = nums1.length;
        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 ++){
                if(nums1[i - 1] == nums2[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[m][n];
    }
}
class Solution {
public:
    int solve(int n1,int n2,vector<int>& nums1, vector<int>& nums2,vector<vector<int>> &dp)
    {
        if(n1<0 || n2<0)
            return 0;
        
        if(dp[n1][n2]!=-1)
            return dp[n1][n2];
        
        if(nums1[n1]==nums2[n2])
            return dp[n1][n2]=1+solve(n1-1,n2-1,nums1,nums2,dp);
        
        return dp[n1][n2]=max(solve(n1-1,n2,nums1,nums2,dp),solve(n1,n2-1,nums1,nums2,dp));
    }
    
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int n1=nums1.size(),n2=nums2.size();
        vector<vector<int>> dp(n1+1,vector<int>(n2+1,-1));
        
        return solve(n1-1,n2-1,nums1,nums2,dp);
    }
};
/** https://leetcode.com/problems/uncrossed-lines/
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var maxUncrossedLines = function(nums1, nums2) {
  // Array to hold the combination of connected numbers
  let dp = [];
  
  // We look up the connected numbers with matrix
  for (let i=0;i< nums1.length;i++){
    for (let j=0;j< nums2.length;j++){
      if (nums1[i]===nums2[j]){
        dp.push([i,j]);
      }
    }
  }
  
  // Only 0 or 1 connected numbers found, return
  if(dp.length <=1){
    return dp.length;
  }
  
  // Array to count how many connected numbers in the matrix without crossing
  let count=Array(dp.length).fill(1);
  let out = count[0];
  
  // Count from the last connected numbers, for each connected number, count how many other connected numbers in front of it that will not crossed with current
  for (let i=dp.length-2;i>=0;i--){
    for (let j=i+1;j<dp.length;j++){
      if (dp[i][0] < dp[j][0]&&
          dp[i][1] < dp[j][1]){
            count[i] = Math.max(count[i],count[j]+1);
            out = Math.max(out, count[i]);
      }
    }
  }
  
  return out;
};
Uncrossed Lines