[1035] 不相交的线

### [1035] 不相交的线

[力扣原题链接](https://leetcode-cn.com/problems/uncrossed-lines/)

在两条独立的水平线上按给定的顺序写下 `nums1` 和 `nums2` 中的整数。

现在，可以绘制一些连接两个数字 `nums1[i]` 和 `nums2[j]` 的直线，这些直线需要同时满足满足：

* `nums1[i] == nums2[j]`
* 且绘制的直线不与任何其他连线（非水平线）相交。

请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。

以这种方法绘制线条，并返回可以绘制的最大连线数。

**示例 1：**

![](/media/202105/2021-05-21_104204.png)

<pre>输入：nums1 = [1,4,2], nums2 = [1,2,4]
输出：2
解释：可以画出两条不交叉的线，如上图所示。 
但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。
</pre>

**示例 2：**

**示例 3：**

**提示：**

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

### 题解

暴力解，基本上所以动规都可以用暴力递归+记表的方式解题。遍历第一个数组，暴力计算第一个数组在第二个数组每个值中出现可以划线的点，由于不能相交，下个点就是从第一个数组的下一个点开始循环遍历第二个数组的下一个点。
[动规解法题解](https://leetcode-cn.com/problems/uncrossed-lines/solution/bu-xiang-jiao-de-xian-by-leetcode-soluti-6tqz/)

### 代码

```cpp
class Solution {
public:
 int helper(vector<int>& nums1,vector<int>& nums2,int begin_1,int begin_2,std::map<int,map<int,int>> &tmp_resurt)
 {
 if(begin_1 >= (int)nums1.size() || begin_2 >= (int)nums2.size()) return 0; //没有点可以连了
 if(tmp_resurt.count(begin_1) > 0 && tmp_resurt[begin_1].count(begin_2) > 0)
 {
 return tmp_resurt[begin_1][begin_2];
 }

int max_count = 0;
 for(int i = begin_1; i < (int)nums1.size(); ++i) //遍历第一个数组
 {
 for(int j = begin_2; j < (int)nums2.size(); ++j) //遍历第二个数组
 {
 if(nums1[i] == nums2[j])
 {
 int son_count = helper(nums1,nums2,i + 1, j + 1,tmp_resurt); //从第一条可以连线开始递归下一条
 max_count = std::max(max_count,son_count + 1); //比较判断最大的连线数
 }
 }
 }

tmp_resurt[begin_1][begin_2] = max_count;   //记表
        return max_count;
    }

int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
 //记表 映射关系为：第一个数组所在点，<第二个数组所在点，从第一个数组点到第二个数组点开始的最大连线>
 std::map<int,map<int,int>> tmp_resurt; 
 return helper(nums1,nums2,0,0,tmp_resurt);
 }
};
```