导读 ^ _ ^
不相交的线本质是最长公共子序列问题。
我们要学会透过现象看本质
题目
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()];
}
};