题目描述
思路解析
一句话答案：LeetCode 1035 不相交的线其实就是求两数组的最长公共子序列 LCS：连线不交叉等价于按原顺序对齐，填 dp[i][j] 表，相等取左上加一、不等取上左较大，时间和空间都 O(m×n)。
1035 到底要连出几条不相交的线
nums1 写上排、nums2 写下排，各按给定顺序。相等才准连一条线，且线不能交叉、每个数最多连一条，问最多连几条。题面 nums1=[1,4,2]、nums2=[1,2,4]，连 1-1、4-4 得 2 条，再补 2-2 会跟 4-4 撞，答案是 2。
连线不能交叉，凭什么就是最长公共子序列
把「不交叉」翻译一下：1-1 连在 4-4 前面，就要求 1 在两排里都排在 4 前面——不交叉，等于对应的数在两排先后顺序一致。这正是从两数组各挑一串、保持原顺序且逐个相等，就是最长公共子序列 LCS（子序列=跳着挑、不必挨着，但保持原顺序）。连线数就等于 LCS 长度。
为什么不能把所有连法都枚举一遍
把所有连线方案摆出来数最大的，随两数组长度指数级膨胀试不完，且大量方案前半截重叠、被反复重算。把「nums1 前 i 个、nums2 前 j 个能连几条」各算一次存起复用，就是动态规划（DP，把『前 i 个、前 j 个能连几条』算一次存下、后面直接取）。
dp[i][j] 定成什么，相等和不等各怎么转移
定义 dp[i][j] 为「只看 nums1 前 i 个、nums2 前 j 个能连出的最大线数」，坐标 (i,j) 是 dp 表第 i 行第 j 列、从 0 数起；第 0 行第 0 列代表「有一排为空」、连不出线全填 0，这圈 0 是转移（转移=怎么从旁边算好的格子推出这一格）的地基。
填内部每格看 nums1 第 i 个和 nums2 第 j 个（代码写成 nums1[i-1]、nums2[j-1]，下标从 0 起）相不相等。相等：能新连一条线，接「两排都退一格」的 dp[i-1][j-1] 加一，dp[i][j]=dp[i-1][j-1]+1。不等：连不了线，取上左较大，dp[i][j]=max(dp[i-1][j], dp[i][j-1])。
拿题面两个数组把整张表填出来
开一张 4×4 表，第 0 行第 0 列全 0，行头 nums1=1、4、2，列头 nums2=1、2、4。第一行对 1：遇 1 相等，左上 0 加一为 1；遇 2、4 不等取较大均为 1。第二行对 4：遇 1、2 不等均为 1；遇 4 相等，左上 1 加一为 2。第三行对 2：遇 1 不等为 1；遇 2 相等，左上 1 加一为 2；遇 4 不等取较大为 2。填到 dp[3][3]=2，即最多线数，与题面对上。
踩左上角加一的有三格——1-1、4-4、2-2，但 4-4 和 2-2 会交叉、只能二选一，最多仍是 2 条。
少留第 0 行第 0 列那圈 0，整张表为什么会算崩
两层循环填满 m×n 格，每格 O(1)，时间 O(m×n)（大 O 记号，操作数随规模怎么涨）；一张二维表，空间 O(m×n)。每格只用左上、上、左三个邻格，可压成一维滚动数组，空间降到 O(min(m,n))。
忘留第 0 行第 0 列那圈 0 最常见，相等时 dp[i-1][j-1] 会越到表外、整张表一路错。另一个坑是当成找连续子串——子序列可跳着挑、按子串会漏解。最后：两数组毫无公共值时整张表仍是 0，答案就是 0。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这套「相等取左上加一，不相等取上、左较大」，下面每填一格都在套它。
先搭表。行头是 nums1=[1,4,2]，列头是 nums2=[1,2,4]，最上一行和最左一列代表「一边为空」，连不出线，全部填 0（蓝色）。接下来从左上往右下一格格填内部。
填 [1,1] 这格：nums1 的 1 和 nums2 的 1 正好相等，可以新连一条线。看它的左上角那格（黄色），在它的基础上加一条。
左上角是 0，加上新连的这一条 = 1。这格落子 1（绿色）。
填 [1,2] 这格：nums1 的 1 和 nums2 的 2 不相等，连不了新线，只能从上面一格和左边一格（两个黄色）里挑大的继承过来。
上面是 0，左边是 1，取较大 = 1。这格落子 1（绿色）。
填 [1,3] 这格：nums1 的 1 和 nums2 的 4 不相等，连不了新线，只能从上面一格和左边一格（两个黄色）里挑大的继承过来。
上面是 0，左边是 1，取较大 = 1。这格落子 1（绿色）。
填 [2,1] 这格：nums1 的 4 和 nums2 的 1 不相等，连不了新线，只能从上面一格和左边一格（两个黄色）里挑大的继承过来。
上面是 1，左边是 0，取较大 = 1。这格落子 1（绿色）。
填 [2,2] 这格：nums1 的 4 和 nums2 的 2 不相等，连不了新线，只能从上面一格和左边一格（两个黄色）里挑大的继承过来。
上面是 1，左边是 1，取较大 = 1。这格落子 1（绿色）。
填 [2,3] 这格：nums1 的 4 和 nums2 的 4 正好相等，可以新连一条线。看它的左上角那格（黄色），在它的基础上加一条。
左上角是 1，加上新连的这一条 = 2。这格落子 2（绿色）。
填 [3,1] 这格：nums1 的 2 和 nums2 的 1 不相等，连不了新线，只能从上面一格和左边一格（两个黄色）里挑大的继承过来。
上面是 1，左边是 0，取较大 = 1。这格落子 1（绿色）。
填 [3,2] 这格：nums1 的 2 和 nums2 的 2 正好相等，可以新连一条线。看它的左上角那格（黄色），在它的基础上加一条。
左上角是 1，加上新连的这一条 = 2。这格落子 2（绿色）。
填 [3,3] 这格：nums1 的 2 和 nums2 的 4 不相等，连不了新线，只能从上面一格和左边一格（两个黄色）里挑大的继承过来。
上面是 2，左边是 2，取较大 = 2。这格落子 2（绿色）。
表填满了。右下角 dp[3][3] = 2，就是最多能连出的线数。
回看哪几步是「相等加一」：整张表其实有三格——[1,1] 连 1-1、[2,3] 连 4-4、[3,2] 连 2-2，都是踩着左上角加一长出来的。但 [2,3](4-4) 和 [3,2](2-2) 这两条会交叉，只能二选一；这条最优连线选了 [1,1] 和 [2,3] 两格（橙色），第三格 [3,2]（蓝色）连上就会和 4-4 撞，所以最多仍是 2 条。
边界先想清：全一致取满、有交叉要取舍、毫无公共值则为 0。
两个高频追问：认出它是 LCS、以及滚动数组压空间。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int: m, n = len(nums1), len(nums2) f = [[0] * (n + 1) for _ in range(m + 1)] for i, x in enumerate(nums1, 1): for j, y in enumerate(nums2, 1): if x == y: f[i][j] = f[i - 1][j - 1] + 1 else: f[i][j] = max(f[i - 1][j], f[i][j - 1]) return f[m][n]复杂度
- 时间：O(m×n)，两层循环填满整张 dp 表，每格 O(1)
- 空间：O(m×n)，一张二维表；可滚动数组压成 O(min(m,n))
易错点
面试追问把动画讲成自己的话
追问这题和「最长公共子序列 LC1143」是什么关系？
追问空间能不能优化？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
分隔数组以得到最大和
LeetCode 1043 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题