前言
题目:1035. 不相交的线
参考题解:不相交的线-代码随想录
提交代码
因为刚敲了leetcode 1143 最长公共子序列,所以能想到本题是对最长公共子序列的应用。要是哪天临时看到这一题,估计会想不出来这个转换关系。
class Solution {
public:
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
// 最长公共子序列的应用
int len1 = nums1.size();
int len2 = nums2.size();
vector<vector<int>> dp(len1+1,vector<int>(len2+1,0));
for(int i=1; i<=len1; i++){
for(int j=1; j<=len2; j++){
if(nums1[i-1] == nums2[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[len1][len2];
}
};