- Problem

1035. Uncrossed Lines

- 내 풀이

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

        dp = [[0 for _ in range(N+1)] for _ in range(M+1)]

        for i in range(M):
            for j in range(N):
                if nums1[i] == nums2[j]:
                    dp[i+1][j+1] = dp[i][j] + 1
                else:
                    dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
        
        return dp[-1][-1]

- 결과

• 시간 복잡도: O(MN)
• 공간 복잡도: O(MN)