題目描述

本題本質上就是求nums1和nums2的最長公共子序列的長度。因此本題本質上與第1143題一模一樣。

代碼：

class Solution {
public:int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {//本題等價于求nums1和nums2的最長公共子序列的長度int len1 = nums1.size();int len2 = nums2.size();//i的取值范圍是[1,len1]//j的取值范圍是[1,len2]//dp[i][j]表示nums1[0,i-1]和nums2[0,j-1]的最長公共子序列的長度//dp[0][j]表示nums1為空,此時不存在公共子序列,dp[0][j]都應該等于0//dp[i][0]表示nums2為空,此時不存在公共子序列,dp[i][0]都應該等于0//i!=0 且 j!=0時，有兩種可能：//如果nums1[i-1]等于nums2[j-1],dp[i][j]=dp[i-1][j-1]+1,dp[i][j]由前面的dp[i-1][j-1]覆蓋,可以不初始化,或者為了編碼方便可以統一初始化為0//如果nums1[i-1]不等于nums2[j-1],dp[i][j]=max(dp[i-1][j],dp[i][j-1]),dp[i][j]由前面的dp[i-1][j]或者dp[i][j-1]覆蓋,可以不初始化,或者為了編碼方便可以統一初始化為0vector<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;elsedp[i][j] = max(dp[i-1][j],dp[i][j-1]);}}return dp[len1][len2];}
};