LeetCode: Uncrossed Linesを解く

問題

May Leetcoding Challange Complementの25日目です。

leetcode.com

解き方

この問題 実はLongest Common Subsequenceとまったく同じ解き方で解けます。
（同じ問題である、という証明ってできるのかな？誰か出来たら教えてください）

blog.pco2699.net

回答

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)