## leetcode weekly contest 134 question 3: 1035. Uncrossed Lines

source

(Gosh I still remembered the happiness when I figured out this DP problem after I stopped doing coding contests for a long, long time.)

At first glance, I correctly guessed that this is a dynamic programming problem. Some thirty seconds later, I sketched a scheme (in my mind in a KFC) for a solution that builds on top of earlier solutions:

`dp[i, j]`

means the answer i.e. maximum number of lines we can draw from the first i characters of A (`A[:i]`

) and first j characters of B (`B[:j]`

)

if there's a line from `A[i]`

to `B[j]`

i.e. if `A[i] == B[j]`

, then `dp[i, j] = dp[i-1, j-1] + 1`

otherwise, `dp[i, j] = max(dp[i-1,j],dp[i,j-1])`

.

This is also explained in the code below (which comes straight from contest).

class Solution: def maxUncrossedLines(self, A: List[int], B: List[int]) -> int: ''' dp[a,b]=max(dp[a-1][b],dp[a][b-1]) if A[a]!=B[b] else: #connect the line 1+dp[a-1][b-1] dp[0,0]=0 if A[a]!=B[b] else 1 return dp[len(A)-1,len(B)-1] ''' dp=[[0 for _ in range(len(B))] for _ in range(len(A))] for a in range(len(A)): for b in range(len(B)): #print(a,b) if a==0 and b==0: dp[a][b] = 0 if A[a] != B[b] else 1 elif a==0: dp[a][b] = dp[a][b-1] if dp[a][b]==0 and A[a] == B[b]: dp[a][b] = 1 elif b==0: dp[a][b] = dp[a-1][b] if dp[a][b]==0 and A[a] == B[b]: dp[a][b] = 1 else: dp[a][b] = max(dp[a-1][b],dp[a][b-1]) if A[a] == B[b]: dp[a][b] = max(dp[a][b],1+dp[a-1][b-1]) #print(dp) return dp[len(A)-1][len(B)-1]