题目: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]; } };