“This is the 19th day of my participation in the First Challenge 2022, for more details: First Challenge 2022”.

1035. Intersecting lines

Topic describes

Write down the integers in nums1 and nums2 on two separate horizontal lines in the given order.

Now, it is possible to draw some lines connecting two numbers nums1[I] and nums2[j] that satisfy both:

  •  nums1[i] == nums2[j]
  • And the drawn line does not intersect any other lines (not horizontal lines).

Note that the lines cannot intersect even at the endpoints: each number can belong to only one line.

Draw a line in this way and return the maximum number of lines that can be drawn.

 

Example 1:

Input: nums1 = [1,4,2], nums2 = [1,2,4] output: 2 explanation: two lines without crossing can be drawn, as shown in the figure above. But a third disjoint line cannot be drawn, because the line from nums1[1]=4 to nums2[2]=4 will intersect the line from nums1[2]=2 to nums2[1]=2.Copy the code

Example 2:

Input: nums1 =,5,1,2,5 [2], nums2 =,5,2,1,5,2 [10] output: 3Copy the code

Example 3:

Input: nums1 =,3,7,1,7,5 [1], nums2 =,9,2,5,1 [1] output: 2Copy the code

parsing

With the previous question (9To find the maximum number of lines drawn is to find the length of the longest common subsequence of two strings./** * @brief; /** * @brief; Dp [I][j] * dp[I][j] * dp[I] * nums1] [I - 1 = = nums2 [j - 1] * at this point, the dp [I] [j] = dp [I - 1] [1] + 1; * nums1[i-1] ! = nums2[j-1] * Dp [I][j] = Max (dp[i-1][j],dp[I][j-1]) * 2,dp[I][j] = Max (dp[i-1][j],dp[I][j]) * 3,dp[I][j] = Max (dp[i-1][j]) * 3,dp[I][j] = Max (DP [i-1][j], DP [I][j]) * 3,dp[I][j] = Max (DP [i-1][j]) * 4,dp[I][j] can be deduced from 3 directions. So you need to traverse from front to back, top to bottom * */

Copy the code

code

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 count = 0;
        for(int i = 1; i<=nums1.size(a); i++){for(int j = 1; j<=nums2.size(a); 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]);
                }

                if(dp[i][j]>count){ count = dp[i][j]; }}}returncount; }};Copy the code