导读 ^ _ ^

不相交的线本质是最长公共子序列问题。
我们要学会透过现象看本质

题目

leetcode 1035

代码与思路

题目本质

• 绘制一些连接两个数字 A[i] 和 B[j] 的直线，只要 A[i] == B[j]，且直线不能相交！
• 本题说是求绘制的最大连线数，其实就是求两个字符串的最长公共子序列的长度！
• 思路和最长子序列一样

遍历答案

//不相交的线
class Solution {
public:
    int maxUncrossedLines(vector<int>& A, vector<int>& B) {
        vector<vector<int>> dp(A.size() + 1, vector<int>(B.size() + 1, 0));
        for (int i = 1; i <= A.size(); i++) {
            for (int j = 1; j <= B.size(); j++) {
                if (A[i - 1] == B[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[A.size()][B.size()];
    }
};

#谢谢你的观看！

^ _ ^