問題
May Leetcoding Challange Complementの25日目です。
解き方
この問題 実はLongest Common Subsequenceとまったく同じ解き方で解けます。
(同じ問題である、という証明ってできるのかな?誰か出来たら教えてください)
回答
class Solution: def maxUncrossedLines(self, A: List[int], B: List[int]) -> int: n1, n2 = len(A), len(B) dp = [[0 for _ in range(n2+1)] for _ in range(n1+1)] for i in range(n1): for j in range(n2): if A[i] == B[j]: dp[i+1][j+1] = dp[i][j] + 1 else: dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]) return dp[-1][-1]
計算量
Aの配列の長さ: M Bの配列の長さ: Nとして
時間計算量: O(M*N)
空間計算量: O(M*N)