leecode1035.不相交的线
这道题看起来可能没有思路，但是实际上仔细观察会发现将相等的数字连接起来，并且不相交，就相当于是元素的原有相对顺序不变求其最大子序和，那么这道题目就是最长公共子序列，代码一模一样
class Solution {
public:
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
int m=nums1.size(),n=nums2.size();
vector<vector<int>> dp(m,vector<int>(n));
dp[0][0]=nums1[0]==nums2[0]?1:0;
for(int j=1;j<n;j++){
if(nums1[0]==nums2[j])
dp[0][j]=1;
else
dp[0][j]=dp[0][j-1];
}
for(int i=1;i<m;i++){
if(nums1[i]==nums2[0])
dp[i][0]=1;
else
dp[i][0]=dp[i-1][0];
for(int j=1;j<n;j++){
if(nums1[i]==nums2[j])
dp[i][j]=dp[i-1][j-1]+1;
else
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
return dp[m-1][n-1];
}
};