We write the integers of A and B (in the order they are given) on two separate horizontal lines.
Now, we may draw connecting lines: a straight line connecting two numbers A[i] and B[j] such that:

A[i] == B[j];
The line we draw does not intersect any other connecting (non-horizontal) line.

Note that a connecting lines cannot intersect even at the endpoints: 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: A = [1,4,2], B = [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 A[1]=4 to B[2]=4 will intersect the line from A[2]=2 to B[1]=2.


Example 2:
Input: A = [2,5,1,2,5], B = [10,5,2,1,5,2]
Output: 3


Example 3:
Input: A = [1,3,7,1,7,5], B = [1,9,2,5,1]
Output: 2
 


Note:

1 <= A.length <= 500
1 <= B.length <= 500
1 <= A[i], B[i] <= 2000

Difficulty: interview

Starter code:

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        

Solutions:
class Solution:
    def maxUncrossedLines(self, A, B):
        # Optimization
        #commons = set(A).intersection(set(B)) # or commons = set(A) & set(B)
        #A = [x for x in A if x in commons]
        #B = [x for x in B if x in commons]

        N1, N2 = len(A), len(B)
        dp = [[0 for _ in range(N2+1)] for _ in range(N1+1)]
        for i1, v1 in enumerate(A, start = 1):
            for i2, v2 in enumerate(B, start = 1):
                if v1 == v2:
                    dp[i1][i2] = dp[i1-1][i2-1] + 1
                else:
                    dp[i1][i2] = max(dp[i1-1][i2], dp[i1][i2-1])
        return dp[N1][N2]
    
class Solution:
    def maxUncrossedLines(self, A, B):
        
        commons = set(A).intersection(set(B)) # or commons = set(A) & set(B)
        A = [x for x in A if x in commons]
        B = [x for x in B if x in commons]
        N1, N2 = len(A), len(B)
        dp = [0 for _ in range(N2+1)]
        for i1, v1 in enumerate(A, start = 1):
            tmp = [0 for _ in range(N2+1)]
            for i2, v2 in enumerate(B, start = 1):
                if v1 == v2:
                    tmp[i2] = dp[i2-1] + 1
                else:
                    tmp[i2] = max(dp[i2], tmp[i2-1])
            dp = tmp
        return dp[N2]
    
from collections import defaultdict
class Solution:
    def maxUncrossedLines(self, A, B):
        f = defaultdict(list)
        for idx, val in enumerate(B):
            f[val].insert(0, idx)
        dp = [0] * len(B)
        for val in A:
            for j in f[val]:
                dp[j] = max(dp[j], max(dp[:j], default=0) + 1)
        return max(dp)

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        dp = [0] * len(B)
        d = {}
        for i in range(len(B)):
            b = B[i]
            if b in d:
                d[b].append(i)
            else:
                d[b] = [i]
        for a in A:
            if a in d:
                for k in d[a][::-1]:
                    if k == 0:
                        dp[k] = 1
                    else:
                        dp[k] = dp[k - 1] + 1
                    for i in range(k + 1, len(dp)):
                        if dp[i] < dp[i - 1]:
                            dp[i] = dp[i - 1]
                        else:
                            break
                    # print(dp)
        return max(dp)
        
                    


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        memo = defaultdict(list)
        
        for i, n in enumerate(B):
            memo[n].append(i)
           
        @lru_cache(None)
        def helper(index, taken):
            if index >= len(A):
                return 0
            count = 0
            if A[index] in memo:
                for i in memo[A[index]]:
                    if i > taken:
                        count = 1 + helper(index+1, i)
                        break
            count = max(count, helper(index+1, taken))
            return count
            
        return helper(0, -1)
            
            


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        memo = {}
        
        def helper(a_idx, b_idx):
            if (a_idx, b_idx) in memo:
                return memo[(a_idx, b_idx)]
            
            if a_idx == len(A) or b_idx == len(B):
                return 0
            
            c1 = 0
            if A[a_idx] == B[b_idx]:
                c1 = 1 + helper(a_idx + 1, b_idx + 1)
            
            c2 = helper(a_idx + 1, b_idx)
            c3 = helper(a_idx, b_idx + 1)
            
            memo[(a_idx, b_idx)] = max(c1, c2, c3)
            
            return memo[(a_idx, b_idx)]
        
        return helper(0, 0)


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        
        dp = {}

        def func(indexA, indexB):
            if indexA == len(A) or indexB == len(B):
                return 0

            if (indexA,indexB) in dp:
                return dp[indexA,indexB]

            if A[indexA] == B[indexB]:
                dp[indexA,indexB] = func(indexA + 1, indexB + 1) + 1
            else:
                dp[indexA,indexB] = max(func(indexA + 1, indexB),func(indexA, indexB + 1))

            return dp[indexA,indexB]
        
        return func(0, 0)

from collections import defaultdict
from functools import lru_cache


class Solution:
    
    @lru_cache(None, False)
    def solve(self, a_from: int, b_from: int):
        if a_from >= len(self.A) or b_from >= len(self.B):
            return 0
        else:
            max_line = 0
            
            for b_pos in self.b_index[self.A[a_from]]:
                if b_pos >= b_from:
                    if_draw = 1 + self.solve(a_from+1, b_pos+1)
                    max_line = max(max_line, if_draw)
            max_line = max(self.solve(a_from+1, b_from), max_line)
            
            return max_line
            
    
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        self.A = A
        self.B = B
        
        self.b_index = defaultdict(list)
        
        for i, b in enumerate(B):
            self.b_index[b].append(i)
        
        return self.solve(0, 0)
            
            


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        
        def help(i, j, mem):
            if i>=len(A) or j>=len(B):
                return 0
            if (i,j) in mem:
                return mem[(i,j)]
            if A[i]==B[j]:
                mem[(i, j)] = 1 + help(i+1, j+1, mem)
                return mem[(i,j)]
            mem[(i, j)] = max(help(i+1, j, mem), help(i, j+1, mem))
            return mem[(i, j)]
        mem = {}
        return help(0, 0, mem)

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        return self.findMaxConnectLines(0, 0, A, B, {})
        
        
    def findMaxConnectLines(self, i, j, A, B, dic):
        if i == len(A) or j == len(B):
            return 0
        
        if (i, j) in dic: return dic[(i, j)]
        
        a = self.findMaxConnectLines(i+1, j, A, B, dic)
        b = float('-inf')
        for k in range(j, len(B)):
            if B[k] == A[i]:
                b = self.findMaxConnectLines(i+1, k+1, A, B, dic) + 1
                break
        dic[(i, j)] = max(a, b)
        return dic[(i, j)]
        
        
        
#   1, 4, 2 ,3, 5
#   1, 2, 3, 5, 4
#   every number has choices: not connect or connect (first encounter connect)
# 


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        memo = {}
        return self.helper(0,0,A,B,memo)
            
    def helper(self,a_index,b_index,A,B,memo):
        if a_index == len(A) or B == len(B):
            return 0
        elif (a_index,b_index) in memo:
            return memo[(a_index,b_index)]
        else:
            put_ = 0
            noput_ = 0
            for i in range(b_index,len(B)):
                if B[i] == A[a_index]:
                    put_ =  1 + self.helper(a_index + 1,i + 1,A,B,memo)
                    break
            noput_ =  self.helper(a_index + 1,b_index,A,B,memo)
            memo[(a_index,b_index)] = max(put_,noput_)
            return memo[(a_index,b_index)]


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        memo = {}
        
        def helper(a_idx, b_idx):
            if a_idx == len(A) or b_idx == len(B):
                return 0
            
            if (a_idx, b_idx) in memo:
                return memo[(a_idx, b_idx)]
            
            c1 = 0
            if A[a_idx] == B[b_idx]:
                c1 = 1 + helper(a_idx + 1, b_idx + 1)
            
            c2 = helper(a_idx + 1, b_idx)
            c3 = helper(a_idx, b_idx + 1)
            
            memo[(a_idx, b_idx)] = max(c1, c2, c3)
            
            return memo[(a_idx, b_idx)]
        
        return helper(0, 0)


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        b_dict = {}
        for idx, b in enumerate(B):
            if b not in b_dict:
                b_dict[b] = []
            b_dict[b].append(idx)
        a_ptrs = []
        for key in b_dict:
            b_dict[key].reverse()
        for a in A:
            if a in b_dict:
                a_ptrs = a_ptrs + b_dict[a]
        lis = []
        for idx, a in enumerate(a_ptrs):
            lis_len = 0
            for i in reversed(range(idx)):
                if a_ptrs[i] < a:
                    lis_len = max(lis_len, lis[i])
            lis_len += 1
            lis.append(lis_len)
        if len(lis) == 0:
            return 0
        return max(lis)

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        if len(A)>len(B): A, B=B, A
        DP=[0]* (len(A)+1)
        coll={j:[-1]+[i for i in range(len(A)) if A[i]==j] for j in set(B)}
        for iB in B[::-1]:
            for i in range(1, len(coll[iB])):
                DP[coll[iB][i]] = max(DP[coll[iB][i]], DP[coll[iB][i]+1]+1)
                for j in range(coll[iB][i], coll[iB][i-1], -1):
                    DP[j]=max(DP[j], DP[j+1])
        return DP[0]


def longest_substr(A, B, i, j, cache):
    if i == len(A) or j == len(B):
        return 0
    
    res = cache.get(i, {}).get(j, None)
    if res is not None:
        return res
    
    length1 = 0
    if A[i] == B[j]:
        length1 = 1 + longest_substr(A, B, i + 1, j + 1, cache)
    length2 = longest_substr(A, B, i + 1, j, cache)
    length3 = longest_substr(A, B, i, j + 1, cache)
    
    length = max(length1, length2, length3)
    cache[i][j] = length
    return length
        


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        cache = defaultdict(dict)
        return longest_substr(A, B, 0, 0, cache)

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        
        from bisect import bisect
        
        a, b = len(A), len(B)
        indA = defaultdict(list)
        indB = defaultdict(list)
        for i,num in enumerate(A):
            indA[num].append(i)
        for i,num in enumerate(B):
            indB[num].append(i)
        
        dp = {}
        for i, num1 in enumerate(A):
            for j, num2 in enumerate(B):
                if num1 == num2:
                    dp[(i,j)] = 1 + (dp[(i-1,j-1)] if min(i,j) > 0 else 0)
                else:
                    ii = bisect(indB[num1], j) if num1 in indB else 0
                    jj = bisect(indA[num2], i) if num2 in indA else 0
                    iii = -1 if ii == 0 else indB[num1][ii-1]
                    jjj = -1 if jj == 0 else indA[num2][jj-1]
                    dp[i,j] = dp[i-1,j-1] if min(i,j)>0 else 0
                    if iii >= 0:
                        dp[i,j] = max(dp[i,j], 1+dp[i-1,iii-1] if min(i,iii)>0 else 1)
                    if jjj >= 0:
                        dp[i,j] = max(dp[i,j], 1+dp[jjj-1,j-1] if min(j,jjj)>0 else 1)
        
        return dp[a-1,b-1]
                          


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        dp = collections.defaultdict(int)
        m, n = len(A), len(B)
        
        for x in range(m):
            for y in range(n):
                cur = 0
                if A[x] == B[y]:
                    cur = 1
                dp[(x, y)] = max(dp[(x - 1, y - 1)] + cur, dp[(x - 1, y)], dp[(x, y - 1)])
                
        return dp[(m - 1, n - 1)]

class Solution:
    def fonction(self, a, b, i, j, dp):
        if j==len(b) or i==len(a):
            return 0
        if dp[i][j]!=-1:
            return dp[i][j]
        if a[i]==b[j]:
            dp[i][j] = 1+self.fonction(a,b,i+1,j+1,dp) 
            return dp[i][j]
        dp[i][j] = max(self.fonction(a,b,i+1,j+1,dp),self.fonction(a,b,i,j+1,dp),self.fonction(a,b,i+1,j,dp))
        return dp[i][j]
    
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        dp = []
        for i in range(len(A)):
            dp.append([-1] * len(B))
        return self.fonction(A,B,0,0,dp)

class Solution:
    def build_value_index_map(self,arr):
        value_idx_map = collections.defaultdict(list)
        
        for i in range(len(arr)):
            value_idx_map[arr[i]].append(i)
        return value_idx_map
        
        
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        
        b_value_idx_map = self.build_value_index_map(B)
        
        
        memo = {}
        
        def helper(a_idx,b_max_idx,memo):
            if a_idx == len(A) or b_max_idx == len(B):
                return 0
            
            
            if (a_idx,b_max_idx) in memo:
                return memo[a_idx,b_max_idx]
            
            curr_num = A[a_idx]                
            res = 0

            for b_idx in b_value_idx_map.get(curr_num,[]):
                if b_idx > b_max_idx:
                    temp = 1 + helper(a_idx+1,b_idx,memo)
                    res = max(res,temp)
            
            memo[a_idx,b_max_idx] = max(res,helper(a_idx+1,b_max_idx,memo))
            return memo[a_idx,b_max_idx]
    
        res=  helper(0,-1,memo)
        return res
            


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        m, n = len(A), len(B)
        if m == 0 or n == 0: return 0
        memo = dict()
        def dfs(i, j):
            if i == m or j == n:
                return 0
            if (i, j) in memo:
                return memo[(i, j)]
            res = max(dfs(i+1, j), dfs(i, j+1))
            if A[i] == B[j]:
                res = max(res, 1 + dfs(i+1, j+1))
            memo[(i, j)] = res
            return res
        return dfs(0, 0)


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        
        B_index = collections.defaultdict(list)
        for i in range(len(B)):
            B_index[B[i]].append(i)
    
        memory = {}
    
        def helper(A_i_, B_i):
            
            A_i = A_i_
            if (A_i, B_i) in memory:
                return memory[(A_i, B_i)]
            
            while A_i < len(A):
                
                # check A match with B:
                if A[A_i] in B_index:
                    for b_i in B_index[A[A_i]]:
                        if b_i < B_i:
                            continue
                        res = max(1 + helper(A_i+1, b_i+1), helper(A_i+1, B_i))
                        memory[(A_i_, B_i)] = res   
                        return res
    
                A_i += 1
            
            memory[(A_i_, B_i)] = 0
            return 0
        
        return helper(0, 0)


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        cache = {}
        def recur(A,B,i,j):
            key = str(i) + '$' + str(j)
            if key in cache:
                return cache[key]
            if i >= len(A) or j >= len(B):
                cache[key] = 0
                return cache[key]
            if A[i] == B[j]:
                cache[key] = 1 + recur(A,B, i + 1, j + 1)
            else:
                cache[key] = max(recur(A,B, i + 1, j), recur(A,B,i,j + 1))
            return cache[key]
        return recur(A,B,0,0);


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        m, n = len(A), len(B)
        dp = [[0] * (n+1) for _ in range(m+1)]
      
        for i in range(1,m+1):
            for j in range(1,n+1):
                left = dp[i][j-1] 
                up = dp[i-1][j]
                leftup = dp[i-1][j-1]
                dp[i][j] = max(left, up, leftup + int(A[i-1]==B[j-1]))
                print(left, up, leftup)
        
        return dp[m][n]

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        dp = []
        for i in range(len(A)):
            dp.append([0] * len(B))

        for i in range(len(A)):
            for j in range(len(B)):
                if A[i] == B[j]:
                    dp[i][j] = max(dp[i][j],1)
                    if i - 1 >= 0 and j - 1 >= 0 :
                        dp[i][j] = max(dp[i][j],dp[i-1][j-1]+1)

                else:
                    if i - 1 >= 0 and j - 1 >= 0:
                        dp[i][j] = max(dp[i][j],dp[i-1][j-1])
                    if j - 1 >= 0:
                        dp[i][j] = max(dp[i][j],dp[i][j-1])
                    if i - 1 >= 0:
                        dp[i][j] = max(dp[i][j],dp[i-1][j])
        return dp[-1][-1]


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        @lru_cache(None)
        def helper(i: int, j: int) -> int:
            if i < 0 or j < 0:
                return 0
            return max([
                helper(i - 1, j - 1) + (A[i] == B[j]),
                helper(i - 1, j),
                helper(i, j - 1)
            ])
        
        return helper(len(A) - 1, len(B) - 1)


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        m, n = len(A), len(B)
        dp = [[0] * n for _ in range(m)]
        
        # dp[0][0] = int(A[0] == B[0])
        
        for i in range(m):
            for j in range(n):
                left = dp[i][j-1] if j>0 else 0
                up = dp[i-1][j] if i>0 else 0
                leftup = dp[i-1][j-1] if i>0 and j>0 else 0
                dp[i][j] = max(left, up, leftup + int(A[i]==B[j]))
                print(left, up, leftup)
        
        return dp[m-1][n-1]

from collections import defaultdict

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:        
        dp = [[0] * (len(B) + 1) for _ in range(len(A) + 1)]
        vals_A = defaultdict(list)
        for i in range(len(A)):
            vals_B = defaultdict(list)
            for j in range(len(B)):
                dp[i + 1][j + 1] = max(dp[i][j], dp[i + 1][j], dp[i][j + 1])
                if A[i] == B[j]:
                    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)

                for pos in vals_A[B[j]]:
                    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[pos][j] + 1)
                for pos in vals_B[A[i]]:
                    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][pos] + 1)

                vals_B[B[j]] += [j]
            
            vals_A[A[i]] += [i]
            
        return dp[len(A)][len(B)]

from collections import defaultdict

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        if len(A) < len(B):
            A, B = B, A
        
        dp = [[0] * (len(B) + 1) for _ in range(len(A) + 1)]
        vals_A = defaultdict(list)
        for i in range(len(A)):
            vals_B = defaultdict(list)
            for j in range(len(B)):
                dp[i + 1][j + 1] = max(dp[i][j], dp[i + 1][j], dp[i][j + 1])
                if A[i] == B[j]:
                    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)

                for pos in vals_A[B[j]]:
                    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[pos][j] + 1)
                for pos in vals_B[A[i]]:
                    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][pos] + 1)

                vals_B[B[j]] += [j]
            
            vals_A[A[i]] += [i]
            
        return dp[len(A)][len(B)]

from collections import defaultdict

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        memo = {}
        
        def r_search(aindex, bindex):
            if aindex == len(A) or bindex == len(B):
                return 0
            if (aindex, bindex) in memo:
                return memo[(aindex, bindex)]
            
            best = 0
            best = max(best, r_search(aindex + 1, bindex))
            best = max(best, r_search(aindex, bindex + 1))
            if A[aindex] == B[bindex]:
                best = max(best, r_search(aindex + 1, bindex + 1) + 1)
            memo[(aindex, bindex)] = best
            return best
        
        return r_search(0, 0)

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        # self.res = float('-inf')
        self.A, self.B = A, B
        self.seen = {}
        return self.dfs(0, 0)
                
    def dfs(self, a, b):
            m, n = len(self.A), len(self.B)
            if a >= m or b >= n:
                return 0
            if (a, b) in self.seen:
                return self.seen[(a, b)]
            
            res = float('-inf')
            cur_b = b
            if self.A[a] == self.B[b]:
                res = max(res, self.dfs(a + 1, b + 1) + 1)
#             while cur_b < n:
#                 if self.A[a] == self.B[cur_b]:
#                     res = max(res, self.dfs(a + 1, cur_b + 1) + 1)
#                     break
#                 cur_b += 1
                
#             cur_a = a
#             while cur_a < m:
#                 # print(cur_a, b)
#                 if self.A[cur_a] == self.B[b]:
#                     res = max(res, self.dfs(cur_a + 1, b + 1) + 1)
#                     break
#                 cur_a += 1
            res = max(res, self.dfs(a + 1, b))
            res = max(res, self.dfs(a, b + 1))
            
            self.seen[(a, b)] = res
            return res

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        # self.res = float('-inf')
        self.A, self.B = A, B
        self.seen = {}
        return self.dfs(0, 0)
                
    def dfs(self, a, b):
            if a >= len(self.A) or b >= len(self.B):
                return 0
            if (a, b) in self.seen:
                return self.seen[(a, b)]
            
            res = float('-inf')
            if self.A[a] == self.B[b]:
                res = max(res, self.dfs(a + 1, b + 1) + 1)
            res = max(res, self.dfs(a + 1, b))
            res = max(res, self.dfs(a, b + 1))
            
            self.seen[(a, b)] = res
            return res

class Solution:
    def getMaxUncrossedLinesFrom(self, A, B, min_a_ix, min_b_ix):
        max_count = 0
        key = (min_a_ix, min_b_ix)
        if key in self.cache:
            return self.cache[key]
        
        for i_a in range(min_a_ix, len(A)):
            val_a = A[i_a]
            b_match_indexes = self.b_lookup.get(val_a)
            if not b_match_indexes:
                continue
            for b_ix in b_match_indexes:
                if b_ix >= min_b_ix:
                    ct = 1 + self.getMaxUncrossedLinesFrom(A, B, i_a + 1, b_ix + 1)
                    max_count = max(max_count, ct)
        self.cache[key] = max_count
        return max_count
    
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        b_lookup = defaultdict(list)
        for i, n in enumerate(B):
            b_lookup[n].append(i)
        self.b_lookup = b_lookup
        self.cache = {}
        
        return self.getMaxUncrossedLinesFrom(A, B, 0, 0)


from functools import lru_cache


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        
        len_a = len(A)
        len_b = len(B)
        
        @lru_cache(None)
        def helper(i, j):
            nonlocal A, B, len_a, len_b, b_index_data

            if i >= len_a or j >= len_b:
                return 0

            ans = float('-inf')
            for x in b_index_data.get(A[i], []):
                if x >= j:
                    ans = 1 + helper(i + 1, x + 1)
                    break
            return max(ans, helper(i + 1, j))

        b_index_data = {}
        for i, val in enumerate(B):
            l = b_index_data.setdefault(val, [])
            l.append(i)

        return helper(0, 0)


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        if len(A) <len(B):
            A,B = B,A
        n = len(B)
        prev = [0] * (n+1)
        for i in range(1,n+1):
            if A[0] == B[i-1]:
                prev[i] = 1
            else:
                prev[i] = prev[i-1]
        curr = [0] * (n+1)
        for i in range(1,len(A)):
            for j in range(1,n+1):
                if A[i] == B[j-1]:
                    curr[j] = 1+prev[j-1]
                else:
                    curr[j] = max(curr[j-1],prev[j])
            prev,curr = curr,prev
        return prev[-1]

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        prev, crnt = [0] * (1 + len(B)), [0] * (1 + len(B))
        for a in range(len(A)):
            prev, crnt = crnt, prev
            for b in range(len(B)):
                if A[a] == B[b]:
                    crnt[b + 1] = prev[b] + 1
                else:
                    crnt[b + 1] = max(crnt[b], prev[b + 1])
        return crnt[len(B)]

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        if len(A)<len(B): A, B=B, A
        DP=[0]* (len(A)+1)
        coll={j:[-1] for j in set(B)}
        for i in range(len(A)):
            if A[i] in coll: coll[A[i]].append(i)
        
        for iB in B[::-1]:
            for i in range(1, len(coll[iB])):
                if DP[coll[iB][i]]<DP[coll[iB][i]+1]+1:
                    DP[coll[iB][i]] = DP[coll[iB][i]+1]+1
                    for j in range(coll[iB][i], coll[iB][i-1], -1):
                        DP[j]=max(DP[j], DP[j+1])
        return DP[0]


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        ga = collections.defaultdict(list)
        # gb = collections.defaultdict(list)
        
        for i, v in enumerate(A):
            ga[v].append(i)
            
        # for j, v in enumerate(B):
        #     gb[v].append(j)
            
        def pd(i, start_a):
            if i >= len(B) or start_a >= len(A):
                return 0
            
            if (i, start_a) in memo:
                return memo[(i, start_a)]
            
            res = pd(i + 1, start_a)
            
            if B[i] in ga:
                
                new_start_a = -1
                
                for cand in ga[B[i]]:
                    if cand > start_a:
                        new_start_a = cand
                        break
                        
                if new_start_a >= start_a:
                    res = max(res, 1 + pd(i + 1, new_start_a))
                
            memo[(i, start_a)] = res
            
            return res
        
        memo = dict()
        
        return pd(0, -1)

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        m = len(A)
        n = len(B)
        dp = [[0] * (n+1) for _ in range(m+1)]
        # dp[0][0] = 1
        for i in range(1, m+1):
            if A[i-1] == B[0]:
                dp[i][1] = 1
        for j in range(1, n+1):
            if B[j-1] == A[0]:
                dp[1][j] = 1
                
        for i, a in enumerate(A, 1):
            for j, b in enumerate(B, 1):
                if a == b:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        return dp[-1][-1]

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        M, N = len(A), len(B)
        dp = [0]*(N+1)
        res = 0
        for i in range(1, M+1):
            dp2 = [0]*(N+1)
            for j in range(1, N+1):
                if A[i-1]==B[j-1]:
                    dp2[j] = dp[j-1]+1
                else:
                    dp2[j] = max(dp[j], dp2[j-1])
            
            dp = dp2
            res = max(res, max(dp))
                
        return res

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        dp = [[0] * (len(B)+1) for _ in range(2)]
        flag = 1
        
        for i in range(len(A)-1, -1, -1):
            for j in range(len(B)-1, -1, -1):
                if A[i] == B[j]:
                    dp[flag][j] = dp[flag^1][j+1] + 1
                else:
                    dp[flag][j] = max(dp[flag][j+1], dp[flag^1][j])
            flag ^= 1
        
        return dp[flag^1][0]


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        A = [-1] + A
        B = [-1] + B
        lenA, lenB = len(A), len(B)
        dp = [[0] * lenA for _ in range(lenB)]
        for y in range(1, lenB):
            for x in range(1, lenA):
                if A[x] == B[y]:
                    dp[y][x] = dp[y-1][x-1] + 1
                else:
                    dp[y][x] = max(dp[y-1][x], dp[y][x-1])
        
        return dp[-1][-1]
    
    
#             A = [ -1 ] + A
#         B = [ -1 ] + B
        
#         h, w = len(A), len(B)
#         dp_table = [ [ 0 for _ in range(w) ] for _ in range(h) ]
        
        
        
#         for y in range(1, h):
#             for x in range(1, w):
                
#                 if A[y] == B[x]:
#                     # current number is matched, add one more uncrossed line
#                     dp_table[y][x] = dp_table[y-1][x-1] + 1
                    
#                 else:
#                     # cuurent number is not matched, backtracking to find maximal uncrossed line
#                     dp_table[y][x] = max( dp_table[y][x-1], dp_table[y-1][x] )

                    
#         return dp_table[-1][-1]


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        
        l,w = len(A), len(B)
        dp = [[0]*(w+1) for _ in range(l+1)]
        for i in range(l):
            for x in range(w):
                if A[i] == B[x]:
                    dp[i+1][x+1] = dp[i][x] + 1
                else:
                    dp[i+1][x+1] = max(dp[i+1][x], dp[i][x+1])
        return dp[-1][-1]

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        if(len(A)==0 or len(B)==0):
            return 0
        A = [ -1 ] + A
        B = [ -1 ] + B
        res = [ [ 0 for _ in range(len(B)) ] for _ in range(len(A)) ]
        for i in range(1,len(A)):
            for j in range(1,len(B)):
                if(A[i]==B[j]):
                    res[i][j]=res[i-1][j-1]+1
                else:
                    res[i][j]=max(res[i-1][j],res[i][j-1])
        return res[-1][-1]
                


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        # A = [-1] + A
#         B = [-1] + B
#         lenA, lenB = len(A), len(B)
#         dp = [[0] * lenB for _ in range(lenA)]
#         for y in range(lenA):
#             for x in range(lenB):
#                 if A[y] == B[x]:
#                     dp[y][x] = dp[y-1][x-1] + 1
#                 else:
#                     dp[y][x] = max(dp[y-1][x], dp[y][x-1])
        
#         return dp[-1][-1]
    
    
        A = [ -1 ] + A
        B = [ -1 ] + B
        
        h, w = len(A), len(B)
        dp_table = [ [ 0 for _ in range(w) ] for _ in range(h) ]
        
        
        
        for y in range(1, h):
            for x in range(1, w):
                
                if A[y] == B[x]:
                    # current number is matched, add one more uncrossed line
                    dp_table[y][x] = dp_table[y-1][x-1] + 1
                    
                else:
                    # cuurent number is not matched, backtracking to find maximal uncrossed line
                    dp_table[y][x] = max( dp_table[y][x-1], dp_table[y-1][x] )

                    
        return dp_table[-1][-1]

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        
        # padding one dummy -1 to represent empty list
        A = [ -1 ] + A
        B = [ -1 ] + B
        
        h, w = len(A), len(B)
        dp_table = [ [ 0 for _ in range(w) ] for _ in range(h) ]
        
        
        
        for y in range(1, h):
            for x in range(1, w):
                
                if A[y] == B[x]:
                    # current number is matched, add one more uncrossed line
                    dp_table[y][x] = dp_table[y-1][x-1] + 1
                    
                else:
                    # cuurent number is not matched, backtracking to find maximal uncrossed line
                    dp_table[y][x] = max( dp_table[y][x-1], dp_table[y-1][x] )

                    
        return dp_table[-1][-1]

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        dp = [[0 for b in range(len(B)+1)] for a in range(len(A)+1)]
        
        for a in range(1, len(A)+1):
            for b in range(1, len(B)+1):
                if A[a-1] == B[b-1]:
                    dp[a][b] = dp[a-1][b-1] + 1
                else:
                    dp[a][b] = max(dp[a-1][b], dp[a][b-1])
        
        return dp[-1][-1]

class Solution:
    def maxUncrossedLines(self, A, B):
        # Optimization
        #commons = set(A).intersection(set(B)) # or commons = set(A) & set(B)
        #A = [x for x in A if x in commons]
        #B = [x for x in B if x in commons]

        N1, N2 = len(A), len(B)
        dp = [[0 for _ in range(N2+1)] for _ in range(N1+1)]
        for i1, v1 in enumerate(A, start = 1):
            for i2, v2 in enumerate(B, start = 1):
                if v1 == v2:
                    dp[i1][i2] = dp[i1-1][i2-1] + 1
                else:
                    dp[i1][i2] = max(dp[i1-1][i2], dp[i1][i2-1])
        return dp[N1][N2]
    
class Solution:
    def maxUncrossedLines(self, A, B):
        
        commons = set(A).intersection(set(B)) # or commons = set(A) & set(B)
        A = [x for x in A if x in commons]
        B = [x for x in B if x in commons]
        N1, N2 = len(A), len(B)
        dp = [0 for _ in range(N2+1)]
        for i1, v1 in enumerate(A, start = 1):
            tmp = [0 for _ in range(N2+1)]
            for i2, v2 in enumerate(B, start = 1):
                if v1 == v2:
                    tmp[i2] = dp[i2-1] + 1
                else:
                    tmp[i2] = max(dp[i2], tmp[i2-1])
            dp = tmp
        return dp[N2]

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        lenA, lenB = len(A), len(B)
        dp = [[0 for _ in range(lenB+1)] for _ in range(lenA + 1) ]
        for i in range(lenA):
            for j in range(lenB):
                if A[i]==B[j]:
                    dp[i+1][j+1] = 1 + dp[i][j]
                else:
                    dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
        #print(dp)
        return dp[lenA][lenB]


class Solution:
    def maxUncrossedLines(self, A, B):
        dp = [[0 for j in range(len(B)+1)] for i in range(len(A)+1)]

        for i in range(1,len(A)+1):
            for j in range(1,len(B)+1):
                if A[i-1] == B[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1])

        return dp[-1][-1]

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        len_a = len(A)+1
        len_b = len(B)+1

        dp = [[0 for i in range(len_b)] for i in range(len_a)]

        for i in range(1, len_a):
            for j in range(1, len_b):
                if A[i - 1] == B[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

        return dp[len_a-1][len_b-1] 

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
                # padding one dummy -1 to represent empty list
        A = [ 1 ] + A
        B = [ 1 ] + B
        
        h, w = len(A), len(B)
        dp_table = [ [ 0 for _ in range(w) ] for _ in range(h) ]
        
        
        
        for y in range(1, h):
            for x in range(1, w):
                
                if A[y] == B[x]:
                    # current number is matched, add one more uncrossed line
                    dp_table[y][x] = dp_table[y-1][x-1] + 1
                    
                else:
                    # cuurent number is not matched, backtracking to find maximal uncrossed line
                    dp_table[y][x] = max( dp_table[y][x-1], dp_table[y-1][x] )

                
        print (dp_table)
        return dp_table[-1][-1]

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        # idea: 0. dp[i, j] is the max number of uncrossed lines in A[0,i] and B[0,j]
        #       1. init: fill dp with 0
        #       2. transition function: loop(expand) B for each in A
        #           dp[i][j] = max(dp[i-1][j],dp[i][j-1]) to have at least the same number supposing when A[i] was expanded, it won't be connected; or B[j] was expanded, it won't be connected;
        #           then if B[j-1] == A[i-1], dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1)
        # time: O( len(A) x len(B) )
        # space:O( len(A) x len(B) )
        
        dp: List[List[int]] = [[0 for i in range(len(B)+1)] for j in range(len(A)+1)]
        for i in range(1, len(A)+1):
            for j in range(1, len(B)+1):
                dp[i][j] = max(dp[i-1][j],dp[i][j-1])
                if B[j-1] == A[i-1]:
                    dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1)
        return dp[len(A)][len(B)]
        
        
        
        


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        La = len(A)
        Lb = len(B)
        dp = [[0]*Lb  for i in range(La)]
        
        for i in range(La):
            for j in range(Lb):
                if i==0:
                    if A[i]==B[j]:
                        dp[i][j] = 1
                    elif j!=0:
                        dp[i][j] = dp[i][j-1]
                else:
                    if j==0:
                        if A[i]==B[j]:
                            dp[i][j] = 1
                        else:
                            dp[i][j] = dp[i-1][j]
                    else:
                        
                        if A[i]==B[j]:
                            dp[i][j] = dp[i-1][j-1] + 1
                        else:
                            dp[i][j] = dp[i-1][j] 
                        dp[i][j] = max(dp[i][j],dp[i][j-1])
        #print(dp)
        return dp[-1][-1]


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        dp = [[0] * (len(B) + 1) for _ in range(len(A) + 1)]
        for i in range(len(A)):
            for j in range(len(B)):
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j], dp[i][j] + (A[i] == B[j]))
        return dp[-1][-1]


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        
        rows = len(A)
        cols = len(B)
        dp = [[0 for i in range(cols+1)] for j in range(rows+1)]
        
        for i in range(rows):
            for j in range(cols):
                if A[i]==B[j]:
                    dp[i+1][j+1]= 1 + dp[i][j]
                else:
                    dp[i+1][j+1]= max(dp[i][j+1],dp[i+1][j],dp[i][j])
        
        return dp[rows][cols]


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        m=len(A)
        n=len(B)
        dp=[[0 for i in range(n+1)] for j in range(m+1)]
        for i in range(1,m+1):
            for j in range(1,n+1):
                if A[i-1]==B[j-1]:
                    dp[i][j]=1+dp[i-1][j-1]
                else:
                    dp[i][j]=max(dp[i][j-1],dp[i-1][j])
        return dp[m][n]

class Solution:
    def maxUncrossedLines(self, A, B):
        # Optimization
        #commons = set(A).intersection(set(B)) # or commons = set(A) & set(B)
        #A = [x for x in A if x in commons]
        #B = [x for x in B if x in commons]

        N1, N2 = len(A), len(B)
        dp = [[0 for _ in range(N2+1)] for _ in range(N1+1)]
        for i1, v1 in enumerate(A, start = 1):
            for i2, v2 in enumerate(B, start = 1):
                if v1 == v2:
                    dp[i1][i2] = dp[i1-1][i2-1] + 1
                else:
                    dp[i1][i2] = max(dp[i1-1][i2], dp[i1][i2-1])
        return dp[N1][N2]
    
class Solution:
    def maxUncrossedLines(self, A, B):
        commons = set(A).intersection(set(B)) # or commons = set(A) & set(B)
        A = [x for x in A if x in commons]
        B = [x for x in B if x in commons]
        N1, N2 = len(A), len(B)
        dp = [0 for _ in range(N2+1)]
        for i1, v1 in enumerate(A, start = 1):
            tmp = [0 for _ in range(N2+1)]
            for i2, v2 in enumerate(B, start = 1):
                if v1 == v2:
                    tmp[i2] = dp[i2-1] + 1
                else:
                    tmp[i2] = max(dp[i2], tmp[i2-1])
            dp = tmp
        return dp[N2]
    


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        dp = [[0 for i in range(len(B) + 1)] for j in range(len(A) + 1)]
        
        for i in range(len(A)):
            for j in range(len(B)):
                if A[i] == B[j]:
                    dp[i + 1][j + 1] = dp[i][j] + 1
                
                else:
                    dp[i + 1][j + 1] = max(dp[i][j], dp[i][j + 1], dp[i + 1][j])

        return dp[-1][-1]

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        if((len_A := len(A)) == 0 or (len_B := len(B)) == 0):
            return 0
        matrix = [[0 for i in range(len_B+1)] for k in range(len_A + 1)]
        for i in range(1, len_A+1):
            for k in range(1, len_B+1):
                if(A[i-1] == B[k-1]):
                    matrix[i][k] = matrix[i-1][k-1] + 1
                else:
                    matrix[i][k] = max(matrix[i-1][k-1], matrix[i-1][k], matrix[i][k-1])
        return matrix[-1][-1]

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        self.result = 0
        mem = collections.defaultdict()
        n = len(A)
        m = len(B)
        def dfs(pos_a, pos_b):
            if pos_a >= n or pos_b >= m:
                return 0
            if (pos_a, pos_b) in mem:
                return mem[(pos_a, pos_b)]
            best = 0
            for i in range(pos_a, n):
                for j in range(pos_b, m):
                    if A[i] == B[j]:
                        best = max(best, dfs(i+1, j+1) + 1)
                    best = max(best, dfs(i+1, j), dfs(i, j+1))
            mem[(pos_a, pos_b)] = best
            return best
        dp = [[0 for _ in range(m+1)] for _ in range(n+1)]
        for i in range(1, n+1):
            for j in range(1, m+1):
                if A[i-1] == B[j-1]:
                    dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1)
                dp[i][j] = max(dp[i][j], dp[i-1][j], dp[i][j-1])
        return dp[-1][-1]
        #return dfs(0, 0)


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        if not A or not B:
            return 0
        
        dp = [[0 for _ in range(len(A)+1)] for _ in range(len(B)+1)]
        
        for i in range(len(B)+1):
            for j in range(len(A)+1):
                if i==0 or j==0:
                    dp[i][j]=0
                elif B[i-1]==A[j-1]:
                    dp[i][j] = dp[i-1][j-1]+1
                else:
                    dp[i][j] = max(dp[i][j-1],dp[i-1][j])
                
        return dp[-1][-1]

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        memo = [[0]*len(A) for _ in range(len(B))]
        
        for i in range(len(memo)):
            for j in range(len(memo[0])):
                
                if B[i] == A[j]:
                    memo[i][j] = 1
                    if i-1 >= 0 and j-1 >= 0:
                        memo[i][j] += memo[i-1][j-1]
                sub_a = 0
                if j-1 >= 0:
                    sub_a = memo[i][j-1] 
                sub_b = 0
                if i-1 >= 0:
                    sub_b = memo[i-1][j]
                memo[i][j] = max(memo[i][j], sub_a, sub_b)
        return memo[-1][-1]


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        len_a = len(A)
        dp = [0] * len_a
        for n in B:
            prev = dp[0]
            if n == A[0]:
                dp[0] = 1
            for idx in range(1,len_a):
                if n == A[idx]:
                    prev, dp[idx] = dp[idx],prev+1
                else:
                    prev, dp[idx] = dp[idx],max(dp[idx-1], dp[idx])

        return dp[-1]


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        M, N = len(A), len(B)
        dp = [[0]*(N+1) for _ in range(M+1)]
        res = 0
        for i in range(1, M+1):
            for j in range(1, N+1):
                if A[i-1]==B[j-1]:
                    dp[i][j] = dp[i-1][j-1]+1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
                    
                res = max(res, dp[i][j])
                
        return res

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        max_lines = 0
        dp = [[0]*(len(B)+1) for _ in range(len(A)+1)]
        for i in range(1,len(A)+1):
            for j in range(1,len(B)+1):
                temp = int(A[i-1]==B[j-1])
                dp[i][j] = max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]+temp)
        return dp[-1][-1]


class Solution:
    # Time Onm
    # Space Onm
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        l1, l2 = len(A), len(B)
        lcs = [[0] * (l1+1) for _ in range(l2+1)]
        # print(lcs)
        for i in range(1, l2+1):
            for j in range(1, l1+1):
                lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1], lcs[i-1][j-1]+(B[i-1]==A[j-1]))
        return lcs[l2][l1]


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        m, n = len(A), len(B)
        dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
        for i in range(m + 1):
            dp[i][0] = 0
        
        for i in range(n + 1):
            dp[0][i] = 0
            
        ret = 0
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                dp[i][j] = dp[i-1][j-1] + 1 if A[i-1] == B[j-1] else max(dp[i-1][j], dp[i][j-1])
                ret = max(ret, dp[i][j])
            
        
        return ret

class Solution:
    def maxUncrossedLines(self, A, B):
        # Optimization
        commons = set(A).intersection(set(B)) # or commons = set(A) & set(B)
        A = [x for x in A if x in commons]
        B = [x for x in B if x in commons]

        N, M = len(A), len(B)
        dp = [[0] * (M + 1) for _ in range(N + 1)]
        for i in range(N):
            for j in range(M):
                if A[i] == B[j]:
                    dp[i + 1][j + 1] = dp[i][j] + 1
                else:
                    dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
        return dp[-1][-1]

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        mat=[[0]*(len(B)+1) for j in range(len(A)+1)]
        for i in range(1,len(A)+1):
            for j in range(1,len(B)+1):
                if A[i-1]==B[j-1]:
                    mat[i][j]=mat[i-1][j-1]+1
                else:
                    mat[i][j]=max(mat[i-1][j],mat[i][j-1])
        return mat[-1][-1]

class Solution:
    
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        # Make a grid of 0's with len(text2) + 1 columns 
        # and len(text1) + 1 rows.
        dp_grid = [[0] * (len(text2) + 1) for _ in range(len(text1) + 1)]
        
        # Iterate up each column, starting from the last one.
        for col in reversed(list(range(len(text2)))):
            for row in reversed(list(range(len(text1)))):
                # If the corresponding characters for this cell are the same...
                if text2[col] == text1[row]:
                    dp_grid[row][col] = 1 + dp_grid[row + 1][col + 1]
                # Otherwise they must be different...
                else:
                    dp_grid[row][col] = max(dp_grid[row + 1][col], dp_grid[row][col + 1])
        
        # The original problem's answer is in dp_grid[0][0]. Return it.
        return dp_grid[0][0]
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        dp_grid = [[0] * (len(B) + 1) for _ in range(len(A) + 1)]
        for col in reversed(list(range(len(B)))):
            for row in reversed(list(range(len(A)))):
                if B[col] == A[row]:
                    dp_grid[row][col] = 1 + dp_grid[row+1][col+1]
                else:
                    dp_grid[row][col] = max(dp_grid[row + 1][col], dp_grid[row][col + 1])
        return dp_grid[0][0]
                
        


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        na, nb = len(A), len(B)
        dp = [[0 for i in range(nb+1)] for j in range(na+1)]
        for i in range(na):
            for j in range(nb): 
                if A[i] == B[j]: dp[i+1][j+1] = 1 + dp[i][j]
                dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j], dp[i][j+1])
        return dp[-1][-1]

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        
        m = len(A)
        n = len(B)
        dp = [[0 for j in range(n+1)] for i in range(m+1)]
        for i in range(m+1):
            for j in range(n+1):
                if(i==0 or j==0):
                    dp[i][j] = 0
                elif(A[i-1]==B[j-1]):
                    dp[i][j] = 1 + dp[i-1][j-1]
                else:
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1])
        
        print(dp)
        return dp[m][n]

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        M, N = len(A), len(B)
        dp = [0] * (N+1)
        for i in range(M):
            for j in range(N)[::-1]:
                if B[j] == A[i]:
                    dp[j+1] = dp[j] + 1
            for j in range(N):
                dp[j+1] = max(dp[j+1], dp[j])
        return dp[-1]
        


class Solution:
     def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        memo = collections.defaultdict(int)
        def maxUncrossedLinesHelper(ai:int, bi:int)->int:
            result = 0
            if ai >= len(A): return 0
            if bi >= len(B): return 0
            if (ai,bi) in memo: return memo[(ai,bi)]
            
            if A[ai] == B[bi]:
                result = maxUncrossedLinesHelper(ai+1, bi+1) + 1
                memo[(ai,bi)] = result
         ##       return result            
            
            chooseA = 0
            try:
                ainb = B.index(A[ai], bi)
            except:
                ainb = -1

            if ainb > 0:
                chooseA = maxUncrossedLinesHelper(ai+1, ainb+1) + 1

            chooseB = 0
            try:
                bina = A.index(B[bi], ai)
            except:
                bina = -1

            if bina > 0:
                chooseB = maxUncrossedLinesHelper(bina+1, bi+1) + 1

            notchooseAB = maxUncrossedLinesHelper(ai+1, bi+1)

            result = max(chooseA, chooseB, notchooseAB,result)
            memo[(ai,bi)] = result
            return result
        
        result = maxUncrossedLinesHelper(0, 0)
        return result


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
                
        a, b = len(A), len(B)
        dp = {}
        for i, num1 in enumerate(A):
            for j, num2 in enumerate(B):
                if num1 == num2:
                    dp[(i,j)] = 1 + dp[i-1,j-1] if min(i,j) > 0 else 1
                else:
                    dp[(i,j)] = max(dp[i-1,j] if i > 0 else 0, 
                                    dp[i,j-1] if j > 0 else 0
                                   )
                 
        return dp[a-1,b-1]
                          


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        # DP : option #1 : Connect A to B
        #      option #2 : Skip B and look for another candidate
        # Longest Common Subsequence
        # if A[i] == B[j], connect and move i-1, j-1
        n, m = len(A), len(B)
        @lru_cache(None)
        def dp(i, j):
            if i < 0 or j < 0: return 0
            if A[i] == B[j]:
                return dp(i-1, j-1) + 1
            return max(dp(i-1, j), dp(i, j-1))
        return dp(n-1, m-1)

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        M,N=len(A),len(B)

        @lru_cache(None)
        def dfs(i,j):
            if i==M or j==N:
                return 0
            if A[i]==B[j]:
                return 1+dfs(i+1,j+1)
            else:
                return max(
                    dfs(i+1,j),
                    dfs(i,j+1)
                )
        
        return dfs(0,0)

class Solution:
  def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
    if len(A) > len(B): return self.maxUncrossedLines(B, A)
    if not A or not B: return 0
#     try:
#       idx = B.index(A[0])
#       return max(1+self.maxUncrossedLines(A[1:], B[idx+1:]), self.maxUncrossedLines(A[1:], B))
#     except:
#       return self.maxUncrossedLines(A[1:], B)
      

# i = 0..len(A)-1    2  5 1 2 5
# j = 0..len(B)-1    10 5 2 1 5 2

    dp = [[0]*len(B) for _ in range(len(A))]
    indexB = collections.defaultdict(list)
    for i, num in enumerate(B):
      indexB[num].append(i)

    for i in reversed(list(range(len(A)))):
      for j in reversed(list(range(len(B)))):
        # find A[i] in B[j:]
        found = False
        for idx in indexB.get(A[i], []):
          if idx >= j: 
            found = True
            break

        if found:
          dp[i][j] = max(1+(dp[i+1][idx+1] if i+1<len(A) and idx+1<len(B) else 0), dp[i+1][j] if i+1<len(A) else 0)
        else:
          dp[i][j] = dp[i+1][j] if i+1 < len(A) else 0
    return dp[0][0]


class Solution:
    def maxUncrossedLines(self, A, B):
        commons = set(A) & set(B)
        A = [x for x in A if x in commons]
        B = [x for x in B if x in commons]
        N1, N2 = len(A), len(B)
        dp = [[0 for _ in range(N2+1)] for _ in range(N1+1)]
        for i1, v1 in enumerate(A, start = 1):
            for i2, v2 in enumerate(B, start = 1):
                if v1 == v2:
                    dp[i1][i2] = dp[i1-1][i2-1] + 1
                else:
                    dp[i1][i2] = max(dp[i1-1][i2], dp[i1][i2-1])
        return dp[N1][N2]
    

    


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        A = [-1] + A
        B = [-1] + B
        
        #142
        #121
        
        #0000
        #0111
        #0111
        #0122
        
        w = len(A)
        h = len(B)
        
        dp_table = [[0 for _ in range(w)]  for _ in range(h) ]
        
        for x in range(1,w):
            for y in range(1,h):
                if A[x] == B[y]:
                    dp_table[y][x] = dp_table[y-1][x-1] +1 
                else:
                    dp_table[y][x] = max(dp_table[y][x-1],dp_table[y-1][x])
        print(dp_table)          
        return dp_table[-1][-1]


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        a = len(A)
        b = len(B)
        memo = {}
        for i in range(a):
            for j in range(b):
                if A[i] == B[j]:
                    memo[(i,j)] = memo.get((i-1, j-1), 0) + 1
                else:
                    memo[(i,j)] = max(memo.get((i-1,j), 0), memo.get((i,j-1), 0))
        return max(memo.values())
                    


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        a = len(A)
        b = len(B)
        memo = {}
        for i in range(a):
            for j in range(b):
                if A[i] == B[j]:
                    memo[(i,j)] = memo.get((i-1, j-1), 0) + 1
                else:
                    memo[(i,j)] = max(memo.get((i-1,j), 0), memo.get((i,j-1), 0))
        return memo.get((a-1, b-1), 0)
                    


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        n = len(A);m = len(B)
        
        @lru_cache(None)
        def fun(i,j):
            if i == n or j == m:
                return 0
            if A[i] == B[j]:
                return 1 + fun(i+1,j+1)
            else:
                return max(fun(i+1,j),fun(i,j+1))
        
        return fun(0,0) 

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        dp = [[0] * (len(B) + 1) for _ in range(len(A) + 1)]
        last_a = {}
        last_b = {}
        for i in range(len(A)):
            last_a[A[i]] = i
            for j in range(len(B)):
                last_b[B[j]] = j
                if A[i] == B[j]:
                    dp[i + 1][j + 1] = max(dp[i][j] + 1, dp[i + 1][j], dp[i][j + 1])
                else:
                    dp[i + 1][j + 1] = max(dp[i][j], dp[i + 1][last_b.get(A[i], -1) + 1], dp[last_a.get(B[j], -1) + 1][j + 1])
        return dp[-1][-1]

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        na, nb = len(A), len(B)
        dp = [[0 for i in range(nb+1)] for j in range(na+1)]
        for i in range(na): 
            for j in range(nb):
                if A[i] == B[j]: dp[i+1][j+1] = 1 + dp[i][j]
                dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1], dp[i+1][j])
        return dp[-1][-1]
                


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

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]

class Solution:
    def maxUncrossedLines(self, A, B):
        # optimization
        commons = set(A).intersection(set(B)) # or commons = set(A) & set(B)
        A = [x for x in A if x in commons]
        B = [x for x in B if x in commons]
        N1, N2 = len(A), len(B)
        dp = [[0 for _ in range(N2+1)] for _ in range(N1+1)]
        for i1, v1 in enumerate(A, start = 1):
            for i2, v2 in enumerate(B, start = 1):
                if v1 == v2:
                    dp[i1][i2] = dp[i1-1][i2-1] + 1
                else:
                    dp[i1][i2] = max(dp[i1-1][i2], dp[i1][i2-1])
        return dp[N1][N2]
    

    


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        m, n = len(A), len(B)
        dp = collections.defaultdict(int)
        for i in range(m):
            for j in range(n):
                match = 1 if A[i] == B[j] else 0
                dp[i, j] = max(dp[i - 1, j - 1] + match, dp[i - 1, j], dp[i, j - 1])
        return dp[m - 1, n - 1]

# https://www.youtube.com/watch?v=7qr4j_fB9S4
# https://leetcode.com/problems/uncrossed-lines/discuss/652102/Python-3-today's-one-liner

class Solution:
  def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
    dp, n, m = defaultdict(int), len(A), len(B)
    for a,b in product(range(n), range(m)):
      dp[a,b] = max(dp[a-1,b-1] + (A[a]==B[b]), dp[a-1,b], dp[a,b-1])
    return dp[n-1, m-1]

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        @lru_cache(None)
        def max_connections(A_index, B_index):
            if A_index > len(A) - 1 or B_index > len(B) - 1:
                return 0

            if A[A_index] == B[B_index]:
                return max(0, 1 + max_connections(A_index + 1, B_index + 1))
            else:
                return max(0, max_connections(A_index + 1, B_index), max_connections(A_index, B_index + 1) )
        
        return max_connections(0, 0) 

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        dp = defaultdict(int)
        N, M = len(A), len(B)
        
        for i in range(N):
            for j in range(M):
                dp[i,j] = max(dp[i-1,j-1] + (A[i] == B[j]), dp[i-1,j], dp[i,j-1])
        return dp[N-1,M-1]

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        m = len(A)
        n = len(B)
        
        dp = [[0] * (n+1) for _ in range(m+1)]

        for i in range(1,m+1):
            for j in range(1,n+1):
                if A[i-1]==B[j-1]:
                    dp[i][j] = dp[i-1][j-1]+1
                
                dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i][j])
                    
        return dp[-1][-1]

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]

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        @lru_cache(maxsize=None)
        def helper(a_idx, b_idx):
            if a_idx == len(A) or b_idx == len(B):
                return 0
            
            c1 = 0
            if A[a_idx] == B[b_idx]:
                c1 = 1 + helper(a_idx + 1, b_idx + 1)
            
            c2 = helper(a_idx + 1, b_idx)
            c3 = helper(a_idx, b_idx + 1)
            
            return max(c1, c2, c3)
        
        return helper(0, 0)


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        if len(A)<len(B): A, B=B, A
        DP=[0]* (len(A)+1)
        coll={j:[-1]+[i for i in range(len(A)) if A[i]==j] for j in set(B)}
        for iB in B[::-1]:
            for i in range(1, len(coll[iB])):
                DP[coll[iB][i]] = max(DP[coll[iB][i]], DP[coll[iB][i]+1]+1)
                for j in range(coll[iB][i], coll[iB][i-1], -1):
                    DP[j]=max(DP[j], DP[j+1])
        return DP[0]


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        m, n = len(A), len(B)
        @lru_cache(None)
        def dfs(i, j):
            if i == -1 or j == -1:
                return 0
            if A[i] == B[j]:
                return dfs(i - 1, j - 1) + 1
            
            return max(dfs(i - 1, j), dfs(i, j - 1))
        
        return dfs(m - 1, n - 1)

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        dp = [[0 for _ in B] for _ in A]
        for i in range(len(B)):
            if A[0] == B[i]:
                dp[0][i] = 1
            elif i != 0:
                dp[0][i] = dp[0][i-1]
        for i in range(len(A)):
            if B[0] == A[i]:
                dp[i][0] = 1
            elif i != 0:
                dp[i][0] = dp[i-1][0]
        for i in range(1,len(A)):
            for j in range(1,len(B)):
                if A[i] == B[j]:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]+1)
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
        return dp[-1][-1]


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        n1 = len(A)
        n2 = len(B)
        dp = [[-1 for _ in range(n2)] for _ in range(n1)]
        return self.recur(0,0,A,B,n1,n2, dp)
    
    def recur(self,i,j,A,B,n1,n2,dp):
        if i == n1 or j == n2:
            return 0
        
        
        if dp[i][j] != -1:
            return dp[i][j]
        if A[i] == B[j]:
            dp[i][j] =  1 + self.recur(i+1,j+1,A,B,n1,n2,dp)
        else:
            c1 = self.recur(i+1,j,A,B,n1,n2,dp)
            c2 = self.recur(i,j+1,A,B,n1,n2,dp)
            dp[i][j] = max(c1,c2)
            
        return dp[i][j]
            


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        max_val = 0
        m, n = len(A), len(B)
        dp = [
            [0 for i in range(n + 1)]
            for j in range(m + 1)
        ]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if A[i - 1] == B[j - 1]:
                    dp[i][j] = max(
                        dp[i-1][j-1] + 1, dp[i-1][j], dp[i][j-1]
                    )
                else:
                    dp[i][j] = max(
                        dp[i-1][j-1], dp[i-1][j], dp[i][j-1]
                    )
                max_val = max(max_val, dp[i][j])
        return max_val


class Solution:

    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        memo = {}
        def helper(A, B, a, b):
            if (a,b) in memo:
                return memo[(a,b)]
            ret = 0
            if a == len(A) or len(B) == b:
                return 0
            if A[a] == B[b]:
                memo[(a,b)] = 1+ helper(A,B, a+1, b+1)
                return memo[(a,b)]
            ret = max(ret, helper(A,B,a, b+1),
                 helper(A,B,a+1, b))
            memo[(a,b)] = ret
            return ret
        return helper(A,B,0,0)

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        
        A = [ -1 ] + A
        B = [ -1 ] + B
        
        dp_table = {}
        
        def helper( idx_a, idx_b ):
            
            if (idx_a, idx_b) in dp_table:
                return dp_table[(idx_a, idx_b)]
            
            
            if idx_a == 0 or idx_b == 0:
                # Any list compared to empty list give no uncrossed line
                return 0
            
            elif A[idx_a] == B[idx_b]:
                
                dp_table[(idx_a, idx_b)] = helper(idx_a-1, idx_b-1) + 1
                return dp_table[(idx_a, idx_b)]
            else:
                dp_table[(idx_a, idx_b)] = max( helper(idx_a-1, idx_b), helper(idx_a, idx_b-1))
                return dp_table[(idx_a, idx_b)]
        
        # --------------------------------------------
        return helper( len(A)-1, len(B)-1 )

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        # Longest common subsequence
        dp = collections.defaultdict(int)
        for i in range(len(A)):
            for j in range(len(B)):
                dp[i, j] = max(dp[i - 1, j - 1] + (A[i] == B[j]), dp[i - 1, j], dp[i, j - 1])
        return dp[len(A) - 1, len(B) - 1]

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        
        l = max(len(A),len(B))
        
        dp = [[-1 for i in range(l+1)]for j in range(l+1)]
    
        def func(indexA, indexB):
            if indexA >= len(A) or indexB >= len(B):
                return 0
            print
            if dp[indexA][indexB] != -1:
                return dp[indexA][indexB]

            if A[indexA] == B[indexB]:
                dp[indexA][indexB] = func(indexA + 1, indexB + 1) + 1
            else:
                dp[indexA][indexB] = max(func(indexA + 1, indexB),func(indexA, indexB + 1))

            return dp[indexA][indexB]

        return func(0, 0)

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
      store = {}    
      a_len = len(A)
      b_len = len(B)
      
      def f(a, b):
        if (a, b) in store: return store[(a, b)]
        
        if a == a_len or b == b_len: 
          store[(a, b)] = 0
          return 0
        
        if A[a] == B[b]:
          store[(a, b)] = 1 + f(a + 1, b + 1)
        else:  
          store[(a, b)] = max(f(a + 1, b), f(a, b + 1))
          
        return store[(a, b)]  
      
      
      return f(0, 0)

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        ab_dict = {a:[] for a in A}
        for i, b in enumerate(B):
            if b in ab_dict:
                ab_dict[b].append(i)
        
        lenA, lenB = len(A), len(B)
        subSolutions = [[None]*lenB for _ in range(lenA)]
        
        def subSolve(i,j):
            if i >= lenA or j >= lenB: return 0
            if subSolutions[i][j]: return subSolutions[i][j]
            if not ab_dict[A[i]]:
                subSolutions[i][j] = 0
                return subSolve(i+1, j)
            if A[i] in ab_dict and j in ab_dict[A[i]]:
                subSolutions[i][j] = 1 + subSolve(i+1, j+1)
                return subSolutions[i][j]
            # if you include A[i]:
            next_j = None
            for b in ab_dict[A[i]]:
                if j < b:
                    next_j = b
                    break
            if next_j is None:
                subSolutions[i][j] = 0
                return subSolve(i+1, j)
            subSolutions[i][j] = max(subSolve(i, next_j), subSolve(i+1, j))
            return subSolutions[i][j]
        
        return subSolve(0,0)

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        m=len(A)
        n=len(B)
        dp=[[0 for _ in range(n+1)] for _ in range(m+1)]
        for i in range(1,m+1):
            for j in range(1,n+1):
                if(A[i-1]==B[j-1]):
                    dp[i][j]=dp[i-1][j-1]+1
                else: 
                    dp[i][j]=max(dp[i][j-1],dp[i-1][j])
        return dp[m][n]


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        A = [ -1 ] + A
        B = [ -1 ] + B
        
        dp_table = {}
        
        def helper( idx_a, idx_b ):
            
            if (idx_a, idx_b) in dp_table:
                return dp_table[(idx_a, idx_b)]
            
            
            if idx_a == 0 or idx_b == 0:
                # Any list compared to empty list give no uncrossed line
                return 0
            
            elif A[idx_a] == B[idx_b]:
                
                dp_table[(idx_a, idx_b)] = helper(idx_a-1, idx_b-1) + 1
                return dp_table[(idx_a, idx_b)]
            else:
                dp_table[(idx_a, idx_b)] = max( helper(idx_a-1, idx_b), helper(idx_a, idx_b-1))
                return dp_table[(idx_a, idx_b)]
        
        # --------------------------------------------
        return helper( len(A)-1, len(B)-1 )        

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        n = len(A);m = len(B)
        
        @lru_cache(None)
        def fun(i,j):
            if i == n or j == m:
                return 0
            loc = -1
            for k in range(j,m):
                if B[k]== A[i]:
                    loc = k
                    break
            if loc == -1:
                return fun(i+1,j)
            else:
                return max(fun(i+1,j),1 + fun(i+1,loc+1))
        
        return fun(0,0) 

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        memo = [[None for i in range(len(B))] for i in range(len(A))]
        return self.uncrossRec(A,B,0,0,memo)
    
    def uncrossRec(self, A: List[int], B: List[int], i: int, j: int, memo):
        if j == len(B) or i == len(A):
            return 0 
        if memo[i][j] != None:
            return memo[i][j]
        if A[i] == B[j]:
            memo[i][j] = 1 + self.uncrossRec(A,B,i+1,j+1,memo)
        else:
            x =self.uncrossRec(A,B,i,j+1,memo)
            y = self.uncrossRec(A,B,i+1,j,memo)
            memo[i][j] = max(x,y)
        return memo[i][j]

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        m,n = len(A),len(B)
        
        grid = [[0 for i in range(n)]for i in range(m)]
        
        for j in range(m):
            for i in range(n):
                av = A[j]
                bv = B[i]
                
                topleft = 0
                top = 0
                left = 0
                if 0 <= j-1 < m and 0 <= i - 1 < n:
                    topleft = grid[j-1][i-1]
                if 0 <= j-1 < m:
                    top = grid[j-1][i]
                if 0 <= i-1 < n:
                    left = grid[j][i-1]
                    
                if av == bv:
                    grid[j][i] = topleft + 1
                else:
                    grid[j][i] = max(top,left)
                
        return grid[-1][-1]

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        nA, nB = len(A), len(B)
        if nA == 0 or nB == 0: return 0
        
        cache = {}
        
        def process(iA, iB):
            if iA < 0 or iB < 0: return 0
            
            if not (iA, iB) in cache:
                ans = 0
                if A[iA] == B[iB]:
                    ans = 1 + process(iA-1, iB-1)
                else:
                    ans = max(process(iA-1, iB), process(iA, iB-1))
                cache[(iA, iB)] = ans
            return cache[(iA, iB)]
        
        return process(nA-1, nB-1)

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        mul_result = {}
        def get_mul(high, low):
            if high == -1 or low == -1:
                return 0
            if (high, low) in mul_result:
                return mul_result[(high, low)]
            result = get_mul(high-1, low-1)
            
            if A[high] in B[:low+1]:
                for i in range(low, -1, -1):
                    if B[i] == A[high]:
                        break
                result = max(result, get_mul(high-1, i-1) + 1)
            
            if B[low] in A[:high+1]:
                for i in range(high, -1, -1):
                    if A[i] == B[low]:
                        break
                result = max(result, get_mul(i-1, low-1) + 1)
            mul_result[(high, low)] = result
            return result
        return get_mul(len(A) - 1, len(B) - 1)


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        N_a=len(A)
        N_b=len(B)
        pair2maxlines=defaultdict(int)
        def max_lines(a,b):
            if pair2maxlines.get((a,b)) is None:
                if a==N_a or b==N_b:
                    pair2maxlines[(a,b)]=0
                    return 0
                if A[a]==B[b]:
                    output =1+max_lines(a+1,b+1)
                    pair2maxlines[(a,b)]=output
                    return output
                output = max(max_lines(a+1,b),max_lines(a,b+1))
                pair2maxlines[(a,b)]=output
                return output
            else:
                return pair2maxlines[(a,b)]
        return max_lines(0,0)


class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        n=len(A)
        m=len(B)
        d={}
        def helper(i,j):
            if i==n or j==m:
                return 0
            if (i,j) in d:
                return d[(i,j)]
            if A[i]==B[j]:
                d[(i,j)]=1+helper(i+1,j+1)
            else:
                d[(i,j)]=max(helper(i+1,j),helper(i,j+1))
            return d[(i,j)]
        return helper(0,0)

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        
        def help(i, j, mem):
            if i>=len(A) or j>=len(B):
                return 0
            if (i,j) in mem:
                return mem[(i, j)]
            if A[i]==B[j]:
                mem[(i,j)]= 1+help(i+1, j+1, mem)
                return mem[(i,j)]
            
            mem[(i,j)]= max(help(i,j+1, mem), help(i+1,j,mem))
            return mem[(i,j)]
        mem = {}
        return help(0,0, mem)