Leetcode 1035. Uncrossed Lines

문제

You are given two integer arrays nums1 and nums2. We write the integers of nums1 and nums2 (in the order they are given) on two separate horizontal lines.

We may draw connecting lines: a straight line connecting two numbers nums1[i] and nums2[j] such that:

nums1[i] == nums2[j], and
the line we draw does not intersect any other connecting (non-horizontal) line.
Note that a connecting line cannot intersect even at the endpoints (i.e., each number can only belong to one connecting line).

Return the maximum number of connecting lines we can draw in this way.

• 두 개의 정수 배열 nums1과 nums2가 주어졌습니다. nums1과 nums2의 정수들을 (주어진 순서대로) 두 개의 분리된 수평선 위에 적습니다.

• 다음과 같은 방식으로 연결선을 그릴 수 있습니다. 두 숫자 nums1[i]와 nums2[j]를 연결하는 직선을 그리는데, 다음 조건을 만족해야 합니다.

1. nums1[i] == nums2[j], 그리고
   우리가 그리는 선은 다른 연결선(수평이 아닌)과 교차하지 않아야 합니다.
2. 연결선은 끝점에서도 교차할 수 없습니다 (즉, 각 숫자는 하나의 연결선에만 속할 수 있습니다).

이러한 방식으로 그릴 수 있는 최대 연결선 수를 반환하세요.

예시

nums1 = [1,4,2], nums2 = [1,2,4]

• 최대 2개의 라인을 그릴수 있다.

제한

• $1 <= nums1.length, nums2.length <= 500$
• $1 <= nums1[i], nums2[j] <= 2000$

풀이

• 연결이 이루어지면 이루어진 곳에서 1칸씩 오른쪽으로 넘어가서부터 이을수 있다.
  • Ex. nums1의 0번 <-> nums2의 1번 이 이어지면 그다음부턴 nums1 의 1번부터, nums2 의 2번 부터 연결에 사용 가능
• 연결이 없었다면 이전의 연결중 최대값을 가져온다.

class Solution:
    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
        N1 = len(nums1)
        N2 = len(nums2)

        cache = {}

        def check(n1: int, n2: int):
            if n1 >= N1 or n2 >= N2:
                return 0

            if (n1, n2) in cache:
                return cache[(n1, n2)]

            if nums1[n1] == nums2[n2]:
                ans = check(n1 + 1, n2 + 1) + 1
            else:
                ans = max(check(n1 + 1, n2), check(n1, n2 + 1))

            cache[(n1, n2)] = ans

            return ans

        return check(0, 0)

• 이걸 2D 배열을 사용하게 최적화 하면

class Solution:
    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
        N1 = len(nums1)
        N2 = len(nums2)

        dp = [[0] * (N2 + 1) for _ in range(N1 + 1)]

        for n1 in range(1, N1 + 1):
            for n2 in range(1, N2 + 1):
                if nums1[n1 - 1] == nums2[n2 - 1]:
                    dp[n1][n2] = dp[n1 - 1][n2 - 1] + 1
                else:
                    dp[n1][n2] = max(dp[n1 - 1][n2], dp[n1][n2 - 1])

        return dp[N1][N2]