不相交的线 图解题解

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。

Python

from __future__ import annotations
from 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]

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        int f[m + 1][n + 1];
        memset(f, 0, sizeof(f));
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    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];
    }
};

Java

import java.util.*;
class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[][] f = new int[m + 1][n + 1];
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                } else {
                    f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
                }
            }
        }
        return f[m][n];
    }
}