1035. Uncrossed Lines

1035. Uncrossed Lines

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

문제

풀이(DFS)

DFS 풀이 방식은 만약 nums1, nums2에서 같은 숫자가 있으면 그 다음 인덱스부터 재귀구조 호출을 하는 것이다.
즉 Example 1을 기준으로 본다면 nums1[i], nums2[j]로 두고 i = 0, j = 0일 때 1, 1이므로 서로 같다.
그러면 i=1,j=1부터 다시 시작하는 것이다. i=1이고 j = 2일 때 4, 4로 같으므로 재귀호출을 한다. 하지만 j값이 len(nums2)가 되었으므로 종료한다. 이제 i=2일 때를 보면 j = 1일 때 2,2로 같다. 재귀함수 호출을 한다. 하지만 i가 nums1가 되었으므로 종료한다. 즉 답은 2가 된다.

결과(DFS)

풀이(DP)

위에 테이블은 DP 테이블이다. MAX 최적화를 하기 위해선 이전 MAX값에서 비교하면 되는데, 비교할 때 2가지 경우가 있다. 만약 nums1[i] != nums2[j]이라면 dp[i][j] = max(dp[i-1][j], dp[i][j-1])을 하면 되고 nums1[i] == nums2[j]라면 dp[i][j] = dp[i-1][j-1] + 1하면 된다.

결과(DP)