題目： LeetCode - 1035. Uncrossed Lines

題目說明

給兩個陣列，將陣列中相同的元素連線，連線不能交叉，求最大連線數。

解題思路

其實題目的答案就是兩者的 LCS。
找 LCS 的作法可參考本篇文章：LeetCode - 1143 解題紀錄。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// fast IO
static auto __ = []()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution {
public:
    int maxUncrossedLines(vector<int>& A, vector<int>& B) {
        int m = A.size(), n = B.size();
        auto dp = vector<vector<int>>(m + 1, vector<int>(n + 1));
        for(int i = 1; i <= m; ++i)
            for(int j = 1; j <= n; ++j)
                dp[i][j] = A[i - 1] == B[j - 1] ? dp[i - 1][j - 1] + 1 : max(dp[i - 1][j], dp[i][j - 1]);
        return dp[m][n];
    }
};