线性动态规划：不相交的线（Uncrossed Lines） 题目描述 给定两个整数数组 nums1 和 nums2 ，要求在两个数组中分别绘制连接相同数字的直线，使得这些直线互不相交（即连接相同数字时不能交叉）。每条直线连接 nums1[i] 和 nums2[j] ，其中 nums1[i] == nums2[j] ，且每条直线只能使用一次。求最多可以绘制多少条不相交的直线。 示例 输入： nums1 = [1,4,2], nums2 = [1,2,4] 输出： 2 解释：连接 nums1[0] 和 nums2[0] （数字1），连接 nums1[1] 和 nums2[2] （数字4），两条直线不相交。若连接 nums1[1] 和 nums2[1] （数字4和2），则会与另一条直线交叉。 解题过程 步骤1：问题转化 此问题本质是求两个数组的 最长公共子序列（LCS） 。因为直线不相交等价于在公共子序列中元素的相对顺序保持一致（即子序列的索引递增）。因此，问题转化为求 nums1 和 nums2 的LCS长度。 步骤2：定义动态规划状态 定义 dp[i][j] 表示 nums1 的前 i 个元素（索引0到i-1）和 nums2 的前 j 个元素（索引0到j-1）的最长公共子序列长度。 i 的范围是 0 到 len(nums1) ， j 的范围是 0 到 len(nums2) 。 当 i=0 或 j=0 时，表示一个数组为空，此时 dp[i][j] = 0 。 步骤3：状态转移方程 对于每个 i 和 j （从1开始遍历）： 如果 nums1[i-1] == nums2[j-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：初始化与填表 初始化一个大小为 (len(nums1)+1) × (len(nums2)+1) 的二维数组 dp ，所有元素初始为0。 双层循环遍历 i 从1到 len(nums1) ， j 从1到 len(nums2) ，根据状态转移方程更新 dp[i][j] 。 步骤5：返回结果 最终结果存储在 dp[len(nums1)][len(nums2)] 中，即两个数组完整序列的LCS长度。 举例演示 以 nums1 = [1,4,2], nums2 = [1,2,4] 为例： 初始化 dp 表（尺寸4×4），首行首列为0。 填表过程： 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],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],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 。 复杂度分析 时间复杂度：O(n×m)，其中n和m为两数组长度。 空间复杂度：可优化至O(min(n,m))，通过滚动数组实现。