LC1035. 不相交的线

题目描述

在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。 现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足： nums1[i] == nums2[j] 且绘制的直线不与任何其他连线（非水平线）相交。 请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。 以这种方法绘制线条，并返回可以绘制的最大连线数。

示例 1： Eq3ibwJk1o1B1gxgBk1cfbE6nzg.png

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

示例 2： 输入：nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2] 输出：3

示例 3： 输入：nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1] 输出：2

提示： 1 <= nums1.length, nums2.length <= 500 1 <= nums1[i], nums2[j] <= 2000

题目解析

题目在说什么

想象一下，你有两排数字，一排叫 nums1，一排叫 nums2。比如：

• nums1 = [1, 4, 2]
• nums2 = [1, 2, 4]

现在你可以用笔在上下两排之间画线，把相同的数字连起来。比如：

• 上面的 1 和下面的 1 可以连一条线
• 上面的 4 和下面的 4 可以连一条线
• 上面的 2 和下面的 2 可以连一条线

但是有个规则：这些线不能交叉。什么叫交叉？比如你画了上面第一个 4 连下面最后一个 4，又画了上面最后一个 2 连下面中间的 2，这两条线就会交叉，像十字路口一样，这是不允许的。而且每个数字只能用一次，不能一个数字连两条线。

问题就是：在遵守这些规则的前提下，最多能画多少条线？

思路是怎么来的

这个问题看起来有点复杂，但我们可以换个角度想。

假设我们画了几条线，比如上面第 1 个数字连下面第 2 个数字，上面第 3 个数字连下面第 5 个数字。你会发现，这些线的顺序必须是从左到右依次匹配的。为什么？因为如果上面第 3 个数字连下面第 2 个数字，而上面第 1 个数字连下面第 5 个数字，这两条线就会交叉。

所以实际上，我们是在两个数组中，从左到右依次找相同的数字，而且每次匹配时，两个数组的索引都必须比上一次大。这不就是“最长公共子序列”问题吗？

“最长公共子序列”是什么？举个例子：你有两个字符串 "abcde" 和 "ace"，它们的最长公共子序列是 "ace"，长度是 3。子序列不要求连续，只要顺序一致就行。

我们的问题其实就是：把 nums1 和 nums2 看作两个序列，找出它们的最长公共子序列的长度。因为每条线就相当于一个匹配，而且不能交叉，所以匹配的顺序必须和数组顺序一致，这就是子序列的定义。

所以，我们不需要真的去画线，只需要用动态规划的方法，计算两个数组的“最长公共子序列”长度就行了。

代码逐步拆解

我们来看参考代码，一行一行解释：

int n1 = nums1.length;
int n2 = nums2.length;

这两行是获取两个数组的长度，后面要用。

int[][] dp = new int[n1 + 1][n2 + 1];

这里创建了一个二维数组 dp。为什么是 n1+1 和 n2+1？因为我们要处理空数组的情况。dp[i][j] 表示：只看 nums1 的前 i 个数字和 nums2 的前 j 个数字，最多能画多少条线（也就是最长公共子序列的长度）。

比如 dp[0][3] 表示 nums1 一个数字都不看，只看 nums2 的前 3 个数字，那肯定一条线也画不了，所以是 0。dp[2][0] 同理也是 0。

for (int i = 1; i <= n1; i++) {
    for (int j = 1; j <= n2; j++) {

这里开始两层循环，i 从 1 到 n1，j 从 1 到 n2。注意 i 和 j 都是从 1 开始的，因为我们把 dp[0][*] 和 dp[*][0] 都留给了空数组的情况。

if (nums1[i - 1] == nums2[j - 1]) {
    dp[i][j] = dp[i - 1][j - 1] + 1;
}

这里检查当前两个数字是否相等。注意索引：nums1[i-1] 是第 i 个数字（因为数组从 0 开始），nums2[j-1] 是第 j 个数字。