Problem statement

https://leetcode.com/problems/uncrossed-lines/

Solution

In fact what is asked to find is the longest common subsequence.

We can use dp with states dp[i][j] is the maximum answer for the first i values from the first array and the first j values from the second array. Then, if values are equal, it is optimal to draw line and solve smaller subproblem. If they are not equal, than situation where i is connected to index >j and j is connected to index > i is not possible, so at least one of the two cases dp[i1 - 1][i2] or dp[i1][i2 - 1] holds.

Complexity

It is O(mn) for time and space.

Code

class Solution:
    def maxUncrossedLines(self, A, B):
        A, B = [0] + A, [0] + B
        m, n = len(A), len(B)
        dp = [[0] * n for _ in range(m)]
        dp[0][0] = 1
        for i1 in range(m):
            for i2 in range(n):
                if A[i1] == B[i2]:
                    dp[i1][i2] = dp[i1 - 1][i2 - 1] + 1
                else:
                    dp[i1][i2] = max(dp[i1 - 1][i2], dp[i1][i2 - 1])

        return int(dp[-1][-1] - 1)