1035. Uncrossed Lines

1035. Uncrossed Lines

 

class Solution:
    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
        # 가장 긴 공통 수열 길이 찾는 것과 동일
        len1 = len(nums1)
        len2 = len(nums2)

        dp = [[0] * (len2+1) for _ in range(len1+1)]

        for i in range(1, len1+1):
            for j in range(1, len2+1):
                if nums1[i-1] == nums2[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]