区间动态规划例题：最长重复子数组（多个数组的公共子数组）

题目描述

给定三个整数数组 nums1、nums2 和 nums3，找到它们共有的、最长的连续子数组的长度。
子数组必须是连续的，即子数组在原数组中占据一段连续的位置。
如果不存在这样的公共连续子数组，返回 0。

示例

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

解题思路

本题是“最长公共子数组”问题的扩展，但约束条件更强：

1. 子数组必须是连续的，所以不能像最长公共子序列那样断开。
2. 这里涉及三个数组，而非传统的两个数组，因此状态定义和转移需要相应调整。

核心思想是区间 DP，但更准确的描述是多维连续匹配的动态规划。
我们定义 dp[i][j][k] 表示以 nums1[i-1]、nums2[j-1]、nums3[k-1] 为结尾的公共连续子数组的长度。
注意：下标从1开始，避免处理边界。

状态转移方程

如果 nums1[i-1] == nums2[j-1] == nums3[k-1]，那么：

dp[i][j][k] = dp[i-1][j-1][k-1] + 1

否则：

dp[i][j][k] = 0

因为连续性要求，一旦某个位置不相等，以这个位置结尾的公共连续子数组长度就为 0。

最终答案是所有 dp[i][j][k] 中的最大值。

逐步推导

假设：

nums1 = [1, 2, 3, 2, 1]
nums2 = [3, 2, 1, 4, 7]
nums3 = [2, 1, 4, 7, 3]
长度分别为 n1=5, n2=5, n3=5

定义 dp[n1+1][n2+1][n3+1] 并初始化为 0。

遍历过程（只展示有匹配的情况）：

1. 当 i=2, j=3, k=1：

   • nums1[1]=2, nums2[2]=2, nums3[0]=2，全部相等。
   • dp[2][3][1] = dp[1][2][0] + 1 = 0 + 1 = 1。

2. 当 i=3, j=4, k=2：

   • nums1[2]=3, nums2[3]=1, nums3[1]=1，不全部相等，所以 dp=0。

3. 当 i=3, j=3, k=2：

   • nums1[2]=3, nums2[2]=2, nums3[1]=1，不全部相等，dp=0。

4. 当 i=4, j=4, k=2：

   • nums1[3]=2, nums2[3]=1, nums3[1]=1，不全部相等，dp=0。

5. 当 i=5, j=4, k=2：

   • nums1[4]=1, nums2[3]=1, nums3[1]=1，全部相等。
   • dp[5][4][2] = dp[4][3][1] + 1。

   先看 dp[4][3][1]：

   • 当 i=4, j=3, k=1：
     nums1[3]=2, nums2[2]=2, nums3[0]=2，全部相等。
     dp[4][3][1] = dp[3][2][0] + 1 = 0 + 1 = 1。

   所以 dp[5][4][2] = 1 + 1 = 2。

   这对应子数组 [2, 1]：
   nums1 下标 3~4：[2,1]
   nums2 下标 2~3：[2,1]
   nums3 下标 0~1：[2,1]

最终最大值为 2。

代码实现（Python）

def longest_common_subarray(nums1, nums2, nums3):
    n1, n2, n3 = len(nums1), len(nums2), len(nums3)
    dp = [[[0] * (n3 + 1) for _ in range(n2 + 1)] for _ in range(n1 + 1)]
    max_len = 0
    
    for i in range(1, n1 + 1):
        for j in range(1, n2 + 1):
            for k in range(1, n3 + 1):
                if nums1[i-1] == nums2[j-1] == nums3[k-1]:
                    dp[i][j][k] = dp[i-1][j-1][k-1] + 1
                    max_len = max(max_len, dp[i][j][k])
                # 否则 dp[i][j][k]=0 已初始化为0
    return max_len

# 示例
nums1 = [1, 2, 3, 2, 1]
nums2 = [3, 2, 1, 4, 7]
nums3 = [2, 1, 4, 7, 3]
print(longest_common_subarray(nums1, nums2, nums3))  # 输出 2

复杂度分析

• 时间复杂度：O(n1 × n2 × n3)
  需要三层循环遍历所有组合。
• 空间复杂度：O(n1 × n2 × n3)
  三维 DP 表的大小。

扩展思考

1. 如果数组更多（如 m 个数组），则 DP 维度变为 m 维，时间复杂度 O(∏nᵢ) 会很高。此时可以考虑用哈希表记录所有数组的相同后缀的方法优化，但本题因为数组数量固定为 3，三维 DP 尚可接受。

2. 如果允许非连续的公共子数组，就变成了“最长公共子序列”问题，状态转移会不同。

3. 本题是区间 DP 中“连续匹配”的典型例子，强调了连续性在状态转移中的体现：相等时从上一个位置延续，不等时清零。