题目来源:https://leetcode.cn/problems/uncrossed-lines/description/
C++题解:经过细细一推导,就发现跟力扣 1143. 最长公共子序列-CSDN博客 换汤不换药。
直线不能相交,说明元素顺序不能改变,求可以绘制的最大连线数,即最长公共子序列。
class Solution {
public:
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
int n1 = nums1.size(), n2 = nums2.size();
vector<vector<int>> dp(n1+1, vector<int>(n2+1, 0));
for(int i = 0; i < n1; i++){
for(int j = 0; j < n2; j++) {
if(nums1[i] == nums2[j]) {
dp[i+1][j+1] = dp[i][j]+1;
}
else {
dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
}
}
}
return dp[n1][n2];
}
};