class?Solution?{

????public:

????????int?maxUncrossedLines(vector<int>&?nums1,?vector<int>&?nums2)?{

????????????/*

????????????dp[i][j]:以nums[i-1]结尾的数组与nums[j-1]结尾的数组元素相等且不相交的线的条数

????????????

????????????????""??1???4???2

????????????""??0???0???0???0???

????????????1???0???1???1???1

????????????2???0???1???1???2

????????????4???0???1???2???2

????????????

????????????if(nums[i-1]==nums[j-1])?dp[i][j]=dp[i-1][j-1]+1;

????????????else?dp[i]][j]=max(dp[i-1][j],dp[i][j-1]);如果没有对位相等，只有可能可能交错相等,dp[i][j]只可能来自这两种状态

????????????*/

????????????int?m=nums1.size();

????????????int?n=nums2.size();

????????????vector<vector<int>>dp(m+1,vector<int>(n+1));

????????????for(int?i=1;i<=m;i++){

????????????????for(int?j=1;j<=n;j++){

????????????????????if(nums1[i-1]==nums2[j-1])?dp[i][j]=dp[i-1][j-1]+1;

????????????????????else?dp[i][j]=max(dp[i][j-1],dp[i-1][j]);

????????????????}

????????????}

????????????return?dp[m][n];

????????}

????};

53. 最大子序和