∅ 1 2 4
∅ 0 0 0 0
1 0 ? ? ?
4 0 ? ? ?
2 0 ? ? ?

线性动态规划：不相交的线（Uncrossed Lines） 题目描述 我们有两个整数数组 nums1 和 nums2 ，分别写在一组平行线的上下方。现在需要绘制一些连接两个数组的直线，要求： 每个数字只能被连接一次（即每条直线连接 nums1[i] 和 nums2[j] ，且同一数组内的数字最多被一条线使用）。 直线不能相交（即对于两条连接 (i1, j1) 和 (i2, j2) 的直线，若 i1 < i2 ，则必须有 j1 < j2 ）。 目标是最大化可以绘制的直线数量。 示例 输入： nums1 = [1,4,2], nums2 = [1,2,4] 输出： 2 解释：可以连接 (1,1) 和 (4,4) ，或连接 (1,1) 和 (2,2) ，但最大连接数为 2。 解题过程 步骤 1：问题转化 观察直线不相交的条件：如果 nums1[i] = nums2[j] 且我们连接了 (i, j) ，那么后续连接必须满足索引严格递增。这实际上等价于在 nums1 和 nums2 中寻找一个 公共子序列 ，且子序列的索引顺序必须保持原数组的相对顺序。因此，问题转化为求两个数组的 最长公共子序列（LCS） 。 步骤 2：定义状态 设 dp[i][j] 表示 nums1 的前 i 个元素与 nums2 的前 j 个元素能形成的最长公共子序列的长度（即最大连接数）。 步骤 3：状态转移方程 如果 nums1[i-1] == nums2[j-1] （注意索引从 0 开始，但 dp 索引从 1 开始），则当前数字可以连接，状态继承自左上角： dp[i][j] = dp[i-1][j-1] + 1 如果当前数字不相等，则最大连接数由左侧或上方的状态决定（即跳过 nums1[i-1] 或跳过 nums2[j-1] ）： dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 步骤 4：初始化 当 i=0 或 j=0 时，表示一个数组为空，此时无法连接任何直线，因此 dp[0][j] = 0 ， dp[i][0] = 0 。 步骤 5：填表顺序 按 i 从 1 到 m ， j 从 1 到 n 的顺序填表（ m 和 n 分别为两个数组的长度）。 步骤 6：举例演算 以示例 nums1 = [1,4,2], nums2 = [1,2,4] 为例： 初始化 dp 表（尺寸 4×4，多一行一列用于边界）： 填表过程： i=1, j=1 ： nums1[0]=1 等于 nums2[0]=1 → dp[1][1] = dp[0][0] + 1 = 1 i=1, j=2 ： 1≠2 → dp[1][2] = max(dp[0][2], dp[1][1]) = max(0,1) = 1 i=1, j=3 ： 1≠4 → dp[1][3] = max(0,1) = 1 i=2, j=1 ： 4≠1 → dp[2][1] = max(dp[1][1], dp[2][0]) = max(1,0) = 1 i=2, j=2 ： 4≠2 → dp[2][2] = max(dp[1][2], dp[2][1]) = max(1,1) = 1 i=2, j=3 ： 4=4 → dp[2][3] = dp[1][2] + 1 = 1 + 1 = 2 i=3, j=1 ： 2≠1 → dp[3][1] = max(dp[2][1], dp[3][0]) = 1 i=3, j=2 ： 2=2 → dp[3][2] = dp[2][1] + 1 = 1 + 1 = 2 i=3, j=3 ： 2≠4 → dp[3][3] = max(dp[2][3], dp[3][2]) = max(2,2) = 2 最终 dp[3][3] = 2 即为答案。 步骤 7：复杂度分析 时间复杂度：O(mn)，需要填充 m×n 的 DP 表。 空间复杂度：可优化至 O(min(m,n))，仅保留上一行和当前行的状态。 通过以上步骤，我们成功将问题转化为 LCS 模型，并用动态规划高效求解。