最长重复子数组（二维动态规划解法）

我们来讲解一个经典的线性动态规划问题：最长重复子数组。这个问题的描述如下：

给定两个整数数组 nums1 和 nums2，请返回两个数组中公共的、长度最长的连续子数组的长度（也称为最长公共子数组的长度）。

示例 1
输入：nums1 = [1,2,3,2,1]，nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共连续子数组是 [3,2,1]，长度为 3。

示例 2
输入：nums1 = [0,0,0,0,0]，nums2 = [0,0,0,0,0]
输出：5

解题思路

这是一个二维动态规划问题，因为我们要比较两个序列的连续子数组。定义状态是关键。

步骤 1：定义状态

设 dp[i][j] 表示以 nums1 的第 i-1 个元素和 nums2 的第 j-1 个元素为结尾的最长公共连续子数组的长度。

注意：这里采用 i-1 和 j-1 是为了避免处理边界条件，让代码更简洁。实际上，dp[i][j] 对应的是 nums1[i-1] 和 nums2[j-1]。

步骤 2：状态转移方程

• 如果 nums1[i-1] == nums2[j-1]，那么以这两个元素结尾的公共连续子数组的长度，应该等于以 nums1[i-2] 和 nums2[j-2] 为结尾的公共连续子数组的长度加 1。
  即：dp[i][j] = dp[i-1][j-1] + 1
• 如果 nums1[i-1] != nums2[j-1]，那么以这两个元素结尾的公共连续子数组的长度为 0，因为连续子数组在这里断了。
  即：dp[i][j] = 0

步骤 3：初始化

• 当 i == 0 或 j == 0 时，表示其中一个数组为空，没有公共连续子数组，所以 dp[0][j] = 0，dp[i][0] = 0。

步骤 4：遍历顺序

我们需要遍历 i 从 1 到 m（m 是 nums1 的长度），遍历 j 从 1 到 n（n 是 nums2 的长度），并记录所有 dp[i][j] 中的最大值，即为最终答案。

步骤 5：举例说明

以 nums1 = [1,2,3,2,1]，nums2 = [3,2,1,4,7] 为例，构造 dp 表（大小为 (m+1) × (n+1)）：

初始化第一行和第一列为 0。

表中数字表示以当前行、列对应元素结尾的最长公共连续子数组的长度。
例如，dp[4][2] = 2 表示以 nums1[3]=2 和 nums2[1]=2 结尾的公共连续子数组长度为 2（即子数组 [2,3] 在 nums1 中是 [3,2]，在 nums2 中是 [3,2] 吗？我们来检查一下：
实际对应是：

• nums1 中以索引 3 结尾的连续公共部分：nums1[2]=3 和 nums1[3]=2，与 nums2 中以索引 1 结尾的连续公共部分：nums2[0]=3 和 nums2[1]=2，这两个子数组完全相同 [3,2]，所以长度是 2。
  更清晰地说，dp[4][2] 对应 nums1[3]=2 和 nums2[1]=2 相同，所以看 dp[3][1] 是 1，所以 dp[4][2] = 1+1=2。

最大值出现在 dp[5][3] = 3，对应子数组 [3,2,1]。

复杂度分析

• 时间复杂度：O(m×n)，需要填充一个 (m+1)×(n+1) 的表格。
• 空间复杂度：O(m×n)，可以优化到 O(min(m, n)) 因为每次更新只用到上一行的值。

代码实现（Python）

def findLength(nums1, nums2):
    m, n = len(nums1), len(nums2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    max_len = 0
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if nums1[i - 1] == nums2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                max_len = max(max_len, dp[i][j])
    return max_len

空间优化版本

因为 dp[i][j] 只依赖于 dp[i-1][j-1]，我们可以用一个一维数组，从后向前更新，避免覆盖需要的值。

def findLength(nums1, nums2):
    m, n = len(nums1), len(nums2)
    dp = [0] * (n + 1)
    max_len = 0
    for i in range(1, m + 1):
        for j in range(n, 0, -1):  # 从后向前更新
            if nums1[i - 1] == nums2[j - 1]:
                dp[j] = dp[j - 1] + 1
                max_len = max(max_len, dp[j])
            else:
                dp[j] = 0
    return max_len

总结

这个问题是二维线性动态规划的经典应用，核心在于定义状态 dp[i][j] 为以特定位置结尾的公共连续子数组长度，并通过比较当前元素是否相等来状态转移。这种方法也可以扩展到更复杂的情况，比如允许最多 k 次不匹配的最长公共子数组（你在已讲题目中已提到过类似变种）。