文章目录
-
- 1. 题目来源
- 2. 题目解析
1. 题目来源
链接:1035. 不相交的线
相关题目:[线性dp] 最长公共子序列(模板题+最长公共子序列模型)
2. 题目解析
很明显问题可以转化为
LCS
,问题。且数据范围很小,元素也可以重复出现,故不能转化为
LIS
问题。就用朴素的双重循环解决即可。和
LCS
一模一样。
时间复杂度: O ( n 2 ) O(n^2) O(n2)
空间复杂度: O ( n 2 ) O(n^2) O(n2)
代码:
class Solution {
public:
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size(), m = nums2.size();
vector<vector<int>> f(n + 1, vector<int>(m + 1));
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ ) {
if (nums1[i - 1] == nums2[j - 1]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
else f[i][j] = max(f[i - 1][j], f[i][j - 1]);
}
return f[n][m];
}
};