1035.Uncrossed Lines
===

###### tags: `Medium`,`Array`,`DP`

[1035. Uncrossed Lines](https://leetcode.com/problems/uncrossed-lines/)

### 題目描述

You are given two integer arrays `nums1` and `nums2`. We write the integers of `nums1` and `nums2` (in the order they are given) on two separate horizontal lines.

We may draw connecting lines: a straight line connecting two numbers `nums1[i]` and `nums2[j]` such that:

* `nums1[i]` == `nums2[j]`, and
* the line we draw does not intersect any other connecting (non-horizontal) line.

Note that a connecting line cannot intersect even at the endpoints (i.e., each number can only belong to one connecting line).

Return *the maximum number of connecting lines we can draw in this way.*

### 範例

**Example 1:**


Input: nums1 = [1,4,2], nums2 = [1,2,4]
Output: 2
Explanation: We can draw 2 uncrossed lines as in the diagram.
We cannot draw 3 uncrossed lines, because the line from nums1[1] = 4 to nums2[2] = 4 will intersect the line from nums1[2]=2 to nums2[1]=2.

**Example 2:**

Input: nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
Output: 3

**Example 3:**

Input: nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
Output: 2

**Constraints**:

* 1 <= `nums1.length`, `nums2.length` <= 500
* 1 <= `nums1[i]`, `nums2[j]` <= 2000

### 解答

#### Javascript
讀完題目就覺得超像LCS，快速寫一個遞迴版本立刻TLE...
放上來給大家笑一下

function maxUncrossedLines(nums1, nums2) {
  const m = nums1.length;
  const n = nums2.length;
  function LCS(i, j) {
    if (i === m || j === n) return 0;

    if (nums1[i] === nums2[j]) {
      return LCS(i + 1, j + 1) + 1;
    }

    return Math.max(LCS(i + 1, j), LCS(i, j + 1));
  }

  return LCS(0, 0);
}

下面這個才會過

function maxUncrossedLines(nums1, nums2) {
  const m = nums1.length;
  const n = nums2.length;
  const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (nums1[i - 1] === nums2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      }

      dp[i][j] = Math.max(dp[i][j], dp[i - 1][j], dp[i][j - 1]);
    }
  }

  return dp[m][n];
}

> [name=Marsgoat][time=May 11, 2023]

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int counter =  0;
        int start_y = 0;
        for (int x = 0 ; x< nums1.size(); x++)
        {
            for (int y = start_y; y<nums2.size(); y++)
            {
                if (nums1[x] == nums2[y])
                {
                    counter++;
                    start_y = y + 1;
                    break;
                }
            }
        }
        return counter;
    }
};

上面這個會顯而易見的 Failed，我再想想
> [name=skylanly][time=May 12, 2023]
### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)