Leetcode題解 Python & C#：五月挑戰DAY26 Uncrossed Lines

給兩個數列 A B 分別寫成上下平行，如果 A[i] == B[j] ，那可以用一直線相連，要找出最大沒有交叉的連線數。

做完上一個 contest ，再看這個問題，很自然就會以相似的解法去進行。

這裡有一個特色「兩數列，各取一個兩兩配對，配對後不能重複再用到。」這樣想到可能會有一個表格狀的DP，再應題目做處理。

這題也是這樣。

DP[i][j] 定為該位置上的最大的沒交叉的相連數。

如果位置 A[i] == B[j] ，那 DP[i][j] = 1 再加右下方 DP[i+1][j+1] ，即加上後方的最大沒交叉相連數。

然後 DP[i][j]  = 從自身、右、下三者取最大值，這樣 DP[i][j] 會是最大的沒交叉的相連數。

最後回傳 DP[0][0] 即可。

Python

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        from functools import lru_cache
        ia, ib = 0, 0
        na, nb = len(A), len(B)
        
        @lru_cache(None)
        def dfs(ia, ib):
            if ia > na - 1 or ib > nb - 1:
                return 0
            ans = 1 if A[ia] == B[ib] else 0
            ans = max(ans + dfs(ia+1, ib+1), dfs(ia+1, ib), dfs(ia, ib+1))
            return ans
        
        return dfs(0, 0)

C#

public class Solution {
    public int MaxUncrossedLines(int[] A, int[] B) {
        int[,] dp = new int[A.Length, B.Length];
        dp[A.Length-1, B.Length-1] = A[A.Length - 1] == B[B.Length - 1] ? 1 : 0;
        int lastNum = B[B.Length - 1];
        for(int i = A.Length - 2; i >= 0; i--)
        {
            if(A[i] == lastNum)
                dp[i, B.Length-1] = 1;
            else
                dp[i, B.Length-1] = dp[i+1, B.Length-1];
        }
        lastNum = A[A.Length - 1];
        for(int j = B.Length - 2; j >= 0; j--)
        {
            if(B[j] == lastNum)
                dp[A.Length-1, j] = 1;
            else
                dp[A.Length-1, j] = dp[A.Length-1, j+1];
        }
        
        for(int i = A.Length - 2; i >= 0; i--)            
        {
            for(int j = B.Length - 2; j >= 0; j--)            
            {
                dp[i, j] = dp[i+1, j+1] + (A[i] == B[j] ? 1 : 0);
                dp[i, j] = Math.Max(dp[i, j], dp[i+1, j]);
                dp[i, j] = Math.Max(dp[i, j], dp[i, j+1]);
            }
        }
        return dp[0, 0];
    }
}