> For the complete documentation index, see [llms.txt](https://kerasnoone.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kerasnoone.gitbook.io/garnet/suan-fa/dong-tai-gui-hua/1035-bu-xiang-jiao-de-xian.md).

# \[1035]\[中等]\[动态规划] 不相交的线

## 题目描述

[1035. 不相交的线](https://leetcode-cn.com/problems/uncrossed-lines/)

我们在两条独立的水平线上按给定的顺序写下 A 和 B 中的整数。

现在，我们可以绘制一些连接两个数字 A\[i] 和 B\[j] 的直线，只要 A\[i] == B\[j]，且我们绘制的直线不与任何其他连线（非水平线）相交。

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

示例 1：

![](/files/-MI7Ns_D_RXP6z5Rz5RK)

```
输入：A = [1,4,2], B = [1,2,4]
输出：2
解释：
我们可以画出两条不交叉的线，如上图所示。
我们无法画出第三条不相交的直线，因为从 A[1]=4 到 B[2]=4 的直线将与从 A[2]=2 到 B[1]=2 的直线相交。
```

示例 2：

```
输入：A = [2,5,1,2,5], B = [10,5,2,1,5,2]
输出：3
```

示例 3：

```
输入：A = [1,3,7,1,7,5], B = [1,9,2,5,1]
输出：2
```

提示：

* 1 <= A.length <= 500
* 1 <= B.length <= 500
* 1 <= A\[i], B\[i] <= 2000

## 解题思路

如果想要不相交, 连线的两端, 每个数组中的数字的相对位置要保持一致, 因此就是在求**公共子序列**. 问题转换成了求两个数组的**最长公共子序列**.

```python
class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        n, m = len(A), len(B)
        dp = [[0] * (m + 1) for _ in range(n + 1)]
        max_len = 0

        for i in range(1, n + 1):
            for j in range(1, m + 1):
                if A[i - 1] == B[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                    max_len = max(max_len, dp[i][j])
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return max_len
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/suan-fa/dong-tai-gui-hua/1035-bu-xiang-jiao-de-xian.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.