1035. 不相交的线

发表于 分类于 阅读次数： Waline： 本文字数： 1.4k 阅读时长 ≈ 5 分钟

考点

  • LCS

思路

（从枚举匹配位置到标准 LCS 的收敛）

一、问题抽象与建模

给定两个整数数组： \[ \text{nums1} = (a_1, a_2, \dots, a_{n_1}), \quad \text{nums2} = (b_1, b_2, \dots, b_{n_2}) \] 可以在满足不相交的前提下，连接若干条线：

  • 每条线连接一个 \(a_i\) 与一个 \(b_j\)

  • 若 \((i_1, j_1)\) 与 \((i_2, j_2)\) 是两条线，则必须满足 \[ i_1 < i_2 \iff j_1 < j_2 \]

目标是最大化连线条数。

该约束与“最长公共子序列（LCS）”的索引单调性完全一致，因此该问题等价于 LCS。

二、状态定义（两份代码共用）

两份代码均采用同一状态定义： \[ f[i][j] = \text{nums1 前 } i \text{ 个元素与 nums2 前 } j \text{ 个元素能形成的最大不相交连线数} \] 其中：

  • \(0 \le i \le n_1\)
  • \(0 \le j \le n_2\)

三、初始值（第一份代码）

1
memset(f, 0, sizeof(f));

对应数学含义： \[ f[0][j] = f[i][0] = 0 \] 解释：

  • 任意一侧为空数组时，不可能连线
  • 这是 LCS / 不相交匹配问题的自然边界条件

四、第一份代码的完整逻辑分析

第一份代码（枚举匹配位置版）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    static const int maxn = 5e2 + 5;
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int n1 = nums1.size(), n2 = nums2.size();
        int f[maxn][maxn];
        memset(f, 0, sizeof(f));
        for (int i = 1; i <= n1; ++i) {
            for (int j = 1; j <= n2; ++j) {
                f[i][j] = max(f[i - 1][j], f[i][j - 1]);
                for (int k = j; k >= 1; --k) {
                    if (nums1[i - 1] == nums2[k - 1])
                        f[i][j] = max(f[i][j], f[i - 1][k - 1] + 1);
                }
                for (int k = i; k >= 1; --k) {
                    if (nums1[k - 1] == nums2[j - 1])
                        f[i][j] = max(f[i][j], f[k - 1][j - 1] + 1);
                }
            }
        }
        return f[n1][n2];
    }
};

4.1 继承项（不使用当前元素）

1
f[i][j] = max(f[i - 1][j], f[i][j - 1]);

对应数学形式： \[ f[i][j] \ge \max\bigl(f[i-1][j],\ f[i][j-1]\bigr) \] 含义：

  • 最优解可能不使用 \(a_i\)
  • 或者不使用 \(b_j\)

这是 LCS 中必不可少的“跳过元素”转移。

4.2 第一段枚举：固定 \(a_i\)，寻找最后一次匹配位置

1
2
3
4
for (int k = j; k >= 1; --k) {
    if (nums1[i - 1] == nums2[k - 1])
        f[i][j] = max(f[i][j], f[i - 1][k - 1] + 1);
}

数学含义： \[ \forall k \le j,\quad \text{若 } a_i = b_k,\quad f[i][j] \ge f[i-1][k-1] + 1 \] 解释：

  • 假设最后一条线连接 \((i, k)\)
  • 那么之前的所有线只能来自子问题 \((i-1, k-1)\)
  • 枚举 \(k\) 即“最后一条线在 nums2 中的位置”

4.3 第二段枚举（对称冗余）

1
2
3
4
for (int k = i; k >= 1; --k) {
    if (nums1[k - 1] == nums2[j - 1])
        f[i][j] = max(f[i][j], f[k - 1][j - 1] + 1);
}

这是与 4.2 完全对称的逻辑：

  • 固定 \(b_j\)
  • 枚举最后一条线在 nums1 中的位置

在逻辑覆盖上，与第一段枚举并不增加新的合法方案。

4.4 第一份代码的“完整状态转移”

综合起来，第一份代码实际上计算的是： \[ \boxed{ f[i][j] = \max\left( \begin{aligned} &f[i-1][j],\\ &f[i][j-1],\\ &\max_{\substack{k \le j \\ a_i = b_k}} (f[i-1][k-1] + 1),\\ &\max_{\substack{k \le i \\ a_k = b_j}} (f[k-1][j-1] + 1) \end{aligned} \right) } \]

五、为何第一份代码是正确的？

关键原因只有一句话：

不相交约束强制匹配对的索引单调递增

因此：

  • 若最后一条线是 \((i, k)\)，其之前的最优解一定来自 \((i-1, k-1)\)
  • 第一份代码完整枚举了所有可能的“最后一条线”
  • 同时保留了“不使用当前元素”的继承路径

因此逻辑是完备且正确的。

六、从第一份代码到第二份代码的化简原理

6.1 核心观察（关键一步）

考虑第一段枚举中的最优项： \[ \max_{\substack{k \le j \\ a_i = b_k}} (f[i-1][k-1] + 1) \] 当 \(a_i = b_j\) 时：

  • 由于 \(f[i-1][j-1] \ge f[i-1][k-1]\)（DP 的单调性）
  • 最大值一定在 \(k = j\) 处取得

即： \[ \max_{\substack{k \le j \\ a_i = b_k}} (f[i-1][k-1] + 1) = f[i-1][j-1] + 1 \quad (\text{当 } a_i = b_j) \] 否则（\(a_i \ne b_j\)）：

  • 该项不会优于继承项
  • 已被 max(f[i-1][j], f[i][j-1]) 覆盖

6.2 第二段枚举为何可以删除？

  • 第二段与第一段在逻辑上是对称的
  • 在已存在继承项的前提下，不会产生新的最优值
  • 属于重复覆盖同一最优解空间

七、第二份代码（标准 LCS 形式）

经过上述化简，状态转移自然收敛为： \[ f[i][j] = \begin{cases} \max(f[i-1][j], f[i][j-1]), & a_i \ne b_j \\ \max(f[i-1][j], f[i][j-1], f[i-1][j-1] + 1), & a_i = b_j \end{cases} \] 对应代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    static const int maxn = 5e2 + 5;
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int n1 = nums1.size(), n2 = nums2.size();
        int f[maxn][maxn];
        memset(f, 0, sizeof(f));
        for (int i = 1; i <= n1; ++i) {
            for (int j = 1; j <= n2; ++j) {
                f[i][j] = max(f[i - 1][j], f[i][j - 1]);
                if (nums1[i - 1] == nums2[j - 1])
                    f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
            }
        }
        return f[n1][n2];
    }
};

八、总结

  • 第一份代码： “枚举最后一条线位置”的完全 DP 描述 正确，但时间复杂度高、存在冗余枚举
  • 第二份代码： 利用单调性与不相交约束后的最简形式 即标准 LCS，时间复杂度降为 \(O(n_1 n_2)\)
  • 两者在数学意义上是严格等价的

第二份代码不是“换思路”，而是第一份代码在不丢失任何最优解的前提下的极限化简结果。