1035.不相交的线 (Medium)*

题目描述*

我们在两条独立的水平线上按给定的顺序写下 A 和 B 中的整数。

现在，我们可以绘制一些连接两个数字 A[i] 和 B[j] 的直线，只要 A[i] == B[j]，且我们绘制的直线不与任何其他连线（非水平线）相交。

以这种方法绘制线条，并返回我们可以绘制的最大连线数。

示例*

输入：A = [1,4,2], B = [1,2,4]

输出：2

最多画出 1-1 4-4 两条线

提示*

1 <= A.length <= 500, 1 <= B.length <= 500, 1 <= A[i], B[i] <= 2000

代码*

第一次是在米哈游的笔试中遇到的，看到的时候还想了一会。这其实是一个最长公共子序列 LCS 的问题。动态规划即可。

dp[i][j] 表示对于 A[1...i] 和 B[1...j]，LCS 长度。从而得出状态转移方程：

dp[i][j] = (A[i - 1] == B[j - 1] ? 1 + dp[i - 1][j - 1] : max(dp[i - 1][j], dp[i][j - 1]));

dp 求解 LCS

class Solution {
public:
    int maxUncrossedLines(vector<int>& A, vector<int>& B) {
        int m = A.size(), n = B.size();
        if(m == 0 || n == 0) {
            return 0;
        }
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                dp[i][j] = (A[i - 1] == B[j - 1] ? 1 + dp[i - 1][j - 1] : max(dp[i - 1][j], dp[i][j - 1]));
            }
        }
        return dp[m][n];
    }
};

最后更新: July 23, 2022