最长公共子数组 (Longest Common Subarray)
字数 3718 2025-12-22 03:53:50

好的，我将为你讲解一个你已列题目之外的线性动态规划题目。本次讲解的题目是：

最长公共子数组 (Longest Common Subarray)

1. 题目描述

给定两个整数数组 A 和 B，你需要找出它们连续且相同的最长子数组的长度。

更具体地：
我们定义子数组必须是连续的（即子序列的一种特殊形式，要求元素在原数组中必须连续）。我们的目标是找到 A 中的一个连续子数组和 B 中的一个连续子数组，使得这两个子数组完全相同，并返回这个相同子数组的最大可能长度。

示例1:

  • 输入: A = [1, 2, 3, 2, 1], B = [3, 2, 1, 4, 7]
  • 输出: 3
  • 解释: 最长的公共子数组是 [3, 2, 1]，长度为3。

示例2:

  • 输入: A = [0, 0, 0, 0, 0], B = [0, 0, 0, 0, 0]
  • 输出: 5
  • 解释: 整个数组就是公共子数组。

问题边界:

  • 数组 A 和 B 的长度范围为 [1, 1000]。
  • 数组元素为整数。

2. 为什么这是一道线性动态规划问题？

这个问题与“最长公共子序列（LCS）”很相似，但有一个关键区别：LCS 不要求连续，只要求顺序相同；而“最长公共子数组”要求连续。这种“连续性”的要求，使得我们可以采用一种更聚焦于“局部”的动态规划思路。

核心观察：
如果 A[i] 和 B[j] 是某个公共子数组的最后一个元素，那么这个公共子数组的长度，完全取决于 A[i-1] 和 B[j-1] 是否也相同。如果是，那么长度可以加1；如果不是，那么这个以 A[i] 和 B[j] 结尾的公共子数组长度就只能为1（仅包含它们自己）或0（它们本身也不同）。

这为我们提供了构建状态转移方程的线索。

3. 动态规划思路推导

我们定义状态 dp[i][j]，其中 i 和 j 分别代表数组 A 和 B 的下标。

状态定义：
dp[i][j] 表示以 A[i-1] 和 B[j-1] 为结尾的最长公共子数组的长度。

注意：这里使用 i-1 和 j-1 是为了方便处理边界（即当 i=0 或 j=0 时，代表空数组，没有元素）。这样 dp[i][j] 对应的是 A[0..i-1] 和 B[0..j-1] 这两个前缀数组。

状态转移方程：

  • 如果 A[i-1] == B[j-1]，那么以 A[i-1] 和 B[j-1] 结尾的公共子数组，可以由以 A[i-2] 和 B[j-2] 结尾的公共子数组向后延伸一位得到。因此：
    dp[i][j] = dp[i-1][j-1] + 1
  • 如果 A[i-1] != B[j-1]，那么以它们结尾不可能构成公共子数组，所以：
    dp[i][j] = 0

初始状态：
当 i=0 或 j=0 时，表示其中一个前缀是空数组，那么公共子数组长度自然为0。所以：
dp[0][j] = 0 对于所有 j
dp[i][0] = 0 对于所有 i

最终答案：
我们的答案不是 dp[m][n]（m, n 分别为数组长度），因为 dp[i][j] 记录的是以特定位置结尾的长度。答案应该是整个 dp 表中出现的最大值，即：
answer = max(dp[i][j])，其中 1 <= i <= m, 1 <= j <= n。

4. 逐步解题过程 (以示例1为例)

我们以 A = [1, 2, 3, 2, 1]， B = [3, 2, 1, 4, 7] 为例，进行逐步计算。

  1. 初始化：创建一个大小为 (m+1) x (n+1) 的二维 dp 表，其中 m=5, n=5。所有元素初始化为0。

  2. 逐行计算：

    • i=1 (A[0]=1):
      • j=1 (B[0]=3): 1 != 3, dp[1][1] = 0
      • j=2 (B[1]=2): 1 != 2, dp[1][2] = 0
      • j=3 (B[2]=1): 1 == 1, dp[1][3] = dp[0][2] + 1 = 0 + 1 = 1（出现长度为1的公共子数组）
      • j=4 (B[3]=4): 1 != 4, dp[1][4] = 0
      • j=5 (B[4]=7): 1 != 7, dp[1][5] = 0
    • i=2 (A[1]=2):
      • j=1 (B[0]=3): 2 != 3, dp[2][1] = 0
      • j=2 (B[1]=2): 2 == 2, dp[2][2] = dp[1][1] + 1 = 0 + 1 = 1
      • j=3 (B[2]=1): 2 != 1, dp[2][3] = 0
      • j=4 (B[3]=4): 2 != 4, dp[2][4] = 0
      • j=5 (B[4]=7): 2 != 7, dp[2][5] = 0
    • i=3 (A[2]=3):
      • j=1 (B[0]=3): 3 == 3, dp[3][1] = dp[2][0] + 1 = 0 + 1 = 1
      • j=2 (B[1]=2): 3 != 2, dp[3][2] = 0
      • j=3 (B[2]=1): 3 != 1, dp[3][3] = 0
      • j=4 (B[3]=4): 3 != 4, dp[3][4] = 0
      • j=5 (B[4]=7): 3 != 7, dp[3][5] = 0
    • i=4 (A[3]=2):
      • j=1 (B[0]=3): 2 != 3, dp[4][1] = 0
      • j=2 (B[1]=2): 2 == 2, dp[4][2] = dp[3][1] + 1 = 1 + 1 = 2（出现长度为2的公共子数组 [3, 2]？注意：这里的 dp[3][1] 对应 A[2]=3 和 B[0]=3，所以延伸过来是 A[2..3]=[3, 2] 和 B[0..1]=[3, 2]）
      • j=3 (B[2]=1): 2 != 1, dp[4][3] = 0
      • j=4 (B[3]=4): 2 != 4, dp[4][4] = 0
      • j=5 (B[4]=7): 2 != 7, dp[4][5] = 0
    • i=5 (A[4]=1):
      • j=1 (B[0]=3): 1 != 3, dp[5][1] = 0
      • j=2 (B[1]=2): 1 != 2, dp[5][2] = 0
      • j=3 (B[2]=1): 1 == 1, dp[5][3] = dp[4][2] + 1 = 2 + 1 = 3（关键！dp[4][2]=2 代表 A[2..3]=[3,2] 和 B[0..1]=[3,2] 相同。现在 A[4]=1 和 B[2]=1 也相同，所以可以接上，形成 A[2..4]=[3,2,1] 和 B[0..2]=[3,2,1]，长度为3）
      • j=4 (B[3]=4): 1 != 4, dp[5][4] = 0
      • j=5 (B[4]=7): 1 != 7, dp[5][5] = 0

  3. 寻找最大值：扫描整个 dp 表，最大值是 dp[5][3] = 3。

因此，最终答案是 3，对应的公共子数组是 A[2..4] 和 B[0..2]，即 [3, 2, 1]。

5. 时间复杂度与空间复杂度分析

  • 时间复杂度：我们需要填充一个 (m+1) * (n+1) 的二维表格，每个 dp[i][j] 的计算是 O(1) 的，因此总时间复杂度为 O(m * n)。
  • 空间复杂度：直接使用二维表格，空间复杂度为 O(m * n)。但我们可以注意到，在计算 dp[i][j] 时，它只依赖于左上角 dp[i-1][j-1]。因此，我们可以使用滚动数组优化，只保留上一行（或上一列）的数据，将空间复杂度降低到 O(min(m, n))。

6. 核心要点总结

  1. 状态定义是精髓：dp[i][j] 定义为“以 A[i-1] 和 B[j-1] 结尾”的长度，巧妙地利用连续性要求。
  2. 转移方程简单：相等就加1，不等就归零。
  3. 答案不在最后一个状态：需要在所有状态中取最大值。
  4. 与 LCS 的区别：LCS 的 dp[i][j] 代表“A[0..i-1] 和 B[0..j-1] 的 LCS 长度”，不要求连续，所以即使 A[i-1] != B[j-1]，dp[i][j] 也能从 dp[i-1][j] 或 dp[i][j-1] 转移过来。而本题不行，一旦不等就必须归零，中断连续性。

这个“最长公共子数组”问题，是动态规划中解决“连续子结构”问题的经典案例，希望你通过这个详细的讲解能够透彻理解。

好的，我将为你讲解一个你已列题目之外的线性动态规划题目。本次讲解的题目是： 最长公共子数组 (Longest Common Subarray) 1. 题目描述 给定两个整数数组 A 和 B ，你需要找出它们 连续且相同 的最长子数组的长度。 更具体地： 我们定义子数组必须是连续的（即子序列的一种特殊形式，要求元素在原数组中必须连续）。我们的目标是找到 A 中的一个连续子数组和 B 中的一个连续子数组，使得这两个子数组完全相同，并返回这个相同子数组的最大可能长度。 示例1: 输入: A = [1, 2, 3, 2, 1] , B = [3, 2, 1, 4, 7] 输出: 3 解释: 最长的公共子数组是 [3, 2, 1] ，长度为3。 示例2: 输入: A = [0, 0, 0, 0, 0] , B = [0, 0, 0, 0, 0] 输出: 5 解释: 整个数组就是公共子数组。 问题边界: 数组 A 和 B 的长度范围为 [1, 1000] 。 数组元素为整数。 2. 为什么这是一道线性动态规划问题？ 这个问题与“最长公共子序列（LCS）”很相似，但有一个关键区别：LCS 不要求连续，只要求顺序相同；而“最长公共子数组”要求连续。这种“连续性”的要求，使得我们可以采用一种更聚焦于“局部”的动态规划思路。 核心观察： 如果 A[i] 和 B[j] 是某个公共子数组的 最后一个元素 ，那么这个公共子数组的长度，完全取决于 A[i-1] 和 B[j-1] 是否也相同。如果是，那么长度可以加1；如果不是，那么这个以 A[i] 和 B[j] 结尾的公共子数组长度就只能为1（仅包含它们自己）或0（它们本身也不同）。 这为我们提供了构建状态转移方程的线索。 3. 动态规划思路推导 我们定义状态 dp[i][j] ，其中 i 和 j 分别代表数组 A 和 B 的下标。 状态定义： dp[i][j] 表示以 A[i-1] 和 B[j-1] 为结尾的 最长公共子数组的长度 。 注意：这里使用 i-1 和 j-1 是为了方便处理边界（即当 i=0 或 j=0 时，代表空数组，没有元素）。这样 dp[i][j] 对应的是 A[0..i-1] 和 B[0..j-1] 这两个前缀数组。 状态转移方程： 如果 A[i-1] == B[j-1] ，那么以 A[i-1] 和 B[j-1] 结尾的公共子数组，可以由以 A[i-2] 和 B[j-2] 结尾的公共子数组向后延伸一位得到。因此： dp[i][j] = dp[i-1][j-1] + 1 如果 A[i-1] != B[j-1] ，那么以它们结尾不可能构成公共子数组，所以： dp[i][j] = 0 初始状态： 当 i=0 或 j=0 时，表示其中一个前缀是空数组，那么公共子数组长度自然为0。所以： dp[0][j] = 0 对于所有 j dp[i][0] = 0 对于所有 i 最终答案： 我们的答案不是 dp[m][n] （m, n 分别为数组长度），因为 dp[i][j] 记录的是以特定位置结尾的长度。答案应该是整个 dp 表中出现的 最大值 ，即： answer = max(dp[i][j]) ，其中 1 <= i <= m , 1 <= j <= n 。 4. 逐步解题过程 (以示例1为例) 我们以 A = [1, 2, 3, 2, 1] ， B = [3, 2, 1, 4, 7] 为例，进行逐步计算。 初始化 ：创建一个大小为 (m+1) x (n+1) 的二维 dp 表，其中 m=5 , n=5 。所有元素初始化为0。 逐行计算 ： i=1 (A[ 0 ]=1): j=1 (B[ 0]=3): 1 != 3, dp[1][1] = 0 j=2 (B[ 1]=2): 1 != 2, dp[1][2] = 0 j=3 (B[ 2]=1): 1 == 1, dp[1][3] = dp[0][2] + 1 = 0 + 1 = 1 （出现长度为1的公共子数组） j=4 (B[ 3]=4): 1 != 4, dp[1][4] = 0 j=5 (B[ 4]=7): 1 != 7, dp[1][5] = 0 i=2 (A[ 1 ]=2): j=1 (B[ 0]=3): 2 != 3, dp[2][1] = 0 j=2 (B[ 1]=2): 2 == 2, dp[2][2] = dp[1][1] + 1 = 0 + 1 = 1 j=3 (B[ 2]=1): 2 != 1, dp[2][3] = 0 j=4 (B[ 3]=4): 2 != 4, dp[2][4] = 0 j=5 (B[ 4]=7): 2 != 7, dp[2][5] = 0 i=3 (A[ 2 ]=3): j=1 (B[ 0]=3): 3 == 3, dp[3][1] = dp[2][0] + 1 = 0 + 1 = 1 j=2 (B[ 1]=2): 3 != 2, dp[3][2] = 0 j=3 (B[ 2]=1): 3 != 1, dp[3][3] = 0 j=4 (B[ 3]=4): 3 != 4, dp[3][4] = 0 j=5 (B[ 4]=7): 3 != 7, dp[3][5] = 0 i=4 (A[ 3 ]=2): j=1 (B[ 0]=3): 2 != 3, dp[4][1] = 0 j=2 (B[ 1]=2): 2 == 2, dp[4][2] = dp[3][1] + 1 = 1 + 1 = 2 （出现长度为2的公共子数组 [3, 2] ？注意：这里的 dp[3][1] 对应 A[2]=3 和 B[0]=3 ，所以延伸过来是 A[2..3]=[3, 2] 和 B[0..1]=[3, 2] ） j=3 (B[ 2]=1): 2 != 1, dp[4][3] = 0 j=4 (B[ 3]=4): 2 != 4, dp[4][4] = 0 j=5 (B[ 4]=7): 2 != 7, dp[4][5] = 0 i=5 (A[ 4 ]=1): j=1 (B[ 0]=3): 1 != 3, dp[5][1] = 0 j=2 (B[ 1]=2): 1 != 2, dp[5][2] = 0 j=3 (B[ 2]=1): 1 == 1, dp[5][3] = dp[4][2] + 1 = 2 + 1 = 3 （关键！ dp[4][2]=2 代表 A[2..3]=[3,2] 和 B[0..1]=[3,2] 相同。现在 A[4]=1 和 B[2]=1 也相同，所以可以接上，形成 A[2..4]=[3,2,1] 和 B[0..2]=[3,2,1] ，长度为3） j=4 (B[ 3]=4): 1 != 4, dp[5][4] = 0 j=5 (B[ 4]=7): 1 != 7, dp[5][5] = 0 寻找最大值 ：扫描整个 dp 表，最大值是 dp[5][3] = 3 。 因此，最终答案是 3 ，对应的公共子数组是 A[2..4] 和 B[0..2] ，即 [3, 2, 1] 。 5. 时间复杂度与空间复杂度分析 时间复杂度 ：我们需要填充一个 (m+1) * (n+1) 的二维表格，每个 dp[i][j] 的计算是 O(1) 的，因此总时间复杂度为 O(m * n) 。 空间复杂度 ：直接使用二维表格，空间复杂度为 O(m * n) 。但我们可以注意到，在计算 dp[i][j] 时，它只依赖于左上角 dp[i-1][j-1] 。因此，我们可以使用滚动数组优化，只保留上一行（或上一列）的数据，将空间复杂度降低到 O(min(m, n)) 。 6. 核心要点总结 状态定义是精髓 ： dp[i][j] 定义为“以 A[i-1] 和 B[j-1] 结尾 ”的长度，巧妙地利用连续性要求。 转移方程简单 ：相等就加1，不等就归零。 答案不在最后一个状态 ：需要在所有状态中取最大值。 与 LCS 的区别 ：LCS 的 dp[i][j] 代表“ A[0..i-1] 和 B[0..j-1] 的 LCS 长度”，不要求连续，所以即使 A[i-1] != B[j-1] ， dp[i][j] 也能从 dp[i-1][j] 或 dp[i][j-1] 转移过来。而本题不行，一旦不等就必须归零，中断连续性。 这个“最长公共子数组”问题，是动态规划中解决“连续子结构”问题的经典案例，希望你通过这个详细的讲解能够透彻理解。