2023.05.11 Today's Challenge

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

Uncrossed Lines - LeetCode

단순 한 방향으로 진행하는게 아니라, 양방향으로 봐야되는 케이스가 존재함.
그래서 DP로 풀어야 됨.

class Solution:
    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
        n1, n2 = len(nums1), len(nums2)
        memo = {}
        def solve(i, j):
            if i <= 0 or j <= 0:
                return 0            
            if (i, j) in memo:
                return memo[(i, j)]            
            if nums1[i-1] == nums2[j-1]:
                memo[(i,j)] = 1 + solve(i-1, j-1)
            else:
                memo[(i,j)] = max(solve(i-1, j), solve(i, j-1))            
            return memo[(i, j)]
        return solve(n1, n2)