LeetCode 1035. 不相交的线

Categories:

题目描述
思路分析
1. 解法一：动态规划（推荐）
相似题目

题目描述

✅ 1035. 不相交的线

思路分析

解法一：动态规划（推荐）

核心思路：

将两条线的匹配关系视为两序列的最长公共子序列（LCS）。

用 dp[j] 表示 nums1 前 i 个与 nums2 前 j 个的 LCS 长度。

外层遍历 nums1，内层遍历 nums2，用 prev 保存左上角状态完成滚动更新。

复杂度分析：

时间复杂度：O(n * m)，其中 n 表示 nums1 长度，m 表示 nums2 长度。

空间复杂度：O(m)，其中 m 表示 nums2 长度。

class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;

        // dp[j] 表示 nums1 前 i 个与 nums2 前 j 个的最长公共子序列长度
        int[] dp = new int[m + 1];

        for (int i = 1; i <= n; i++) {
            int prev = 0;

            // 使用滚动数组更新当前行
            for (int j = 1; j <= m; j++) {
                int temp = dp[j];
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[j] = prev + 1;
                } else {
                    dp[j] = Math.max(dp[j], dp[j - 1]);
                }
                prev = temp;
            }
        }

        return dp[m];
    }
}

func maxUncrossedLines(nums1 []int, nums2 []int) int {
	n := len(nums1)
	m := len(nums2)

	// dp[j] 表示 nums1 前 i 个与 nums2 前 j 个的最长公共子序列长度
	dp := make([]int, m+1)

	for i := 1; i <= n; i++ {
		prev := 0

		// 使用滚动数组更新当前行
		for j := 1; j <= m; j++ {
			temp := dp[j]
			if nums1[i-1] == nums2[j-1] {
				dp[j] = prev + 1
			} else if dp[j-1] > dp[j] {
				dp[j] = dp[j-1]
			}
			prev = temp
		}
	}

	return dp[m]
}

相似题目

题目	难度	考察点
1143. 最长公共子序列	中等	动态规划
583. 两个字符串的删除操作	中等	动态规划
712. 两个字符串的最小ASCII删除和	中等	动态规划
72. 编辑距离	困难	动态规划
516. 最长回文子序列	中等	动态规划
718. 最长重复子数组	中等	动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/46471355