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

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

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

Solutions:
class Solution:

	def maxUncrossedLines(self, A, B):
		(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))
		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
		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]


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:
		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):
				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)


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:
		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.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)
		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:
		ga = collections.defaultdict(list)
		for (i, v) in enumerate(A):
			ga[v].append(i)

		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)]
		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]


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
		(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]:
					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])
		return dp_table[-1][-1]


class Solution:

	def maxUncrossedLines(self, A, B):
		(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))
		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, 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:
		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]
				elif 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])
		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:
		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]


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:
		(l1, l2) = (len(A), len(B))
		lcs = [[0] * (l1 + 1) for _ in range(l2 + 1)]
		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, B):
		commons = set(A).intersection(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:
		dp_grid = [[0] * (len(text2) + 1) for _ in range(len(text1) + 1)]
		for col in reversed(list(range(len(text2)))):
			for row in reversed(list(range(len(text1)))):
				if text2[col] == text1[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]

	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:
		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
			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:
		(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
		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)))):
				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: 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:
		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:
		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, 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:

		@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:
		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:
		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:
				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:
		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]
			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:
		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)