不相交的线
动态规划
本题说是求绘制的最大连线数,其实就是求两个字符串的最长公共子序列的长度!
那么本题就和我们刚刚讲过的这道题目动态规划:1143.最长公共子序列 就是一样一样的了。
class Solution { public: int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) { vector<vector<int>> dp(nums1.size()+1 , vector<int>(nums2.size()+1,0)); for(int i=0 ; i<nums1.size();i++) { for(int j=0 ; j<nums2.size();j++) { if(nums1[i]==nums2[j]) dp[i+1][j+1] = dp[i][j]+1; else dp[i+1][j+1] = max(dp[i+1][j] , dp[i][j+1]); } } // for(int i=0 ; i<nums1.size();i++) // { // for(int j=0 ; j<nums2.size();j++) // { // cout<<dp[i][j]<<' '; // } // cout<<endl; // } return dp[nums1.size()][nums2.size()]; } };
二刷
class Solution { public: int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) { vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1 , 0)); int result = 0; for(int i=1 ; i<=nums1.size() ;i++) { for(int j=1 ; j<=nums2.size() ; 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]); } } // for(int i=1 ; i<=nums1.size() ;i++) // { // for(int j=1 ; j<=nums2.size() ; j++) // cout<<dp[i][j]<<' '; // cout<<endl; // } return dp[nums1.size()][nums2.size()]; } };