区间动态规划例题：最长重复子数组问题（两个数组版本） 题目描述 给定两个整数数组 A 和 B （长度分别为 m 和 n ），要求找到它们的最长公共子数组的长度。这里的“公共子数组”指的是连续的子数组。例如，若 A = [1,2,3,2,1] ， B = [3,2,1,4,7] ，则最长公共子数组是 [3,2,1] ，长度为 3。 解题过程 问题分析 与最长公共子序列（LCS）不同，本题要求子数组必须连续。 若使用暴力解法，枚举所有子数组组合，时间复杂度为 O(m² × n²)，不可接受。 关键观察：如果 A[i] 和 B[j] 是公共子数组的结尾元素，那么该子数组的长度取决于 A[i-1] 和 B[j-1] 是否匹配。 定义状态 设 dp[i][j] 表示以 A[i-1] 和 B[j-1] 结尾的最长公共子数组的长度（索引从 1 开始便于处理边界）。 例如， dp[2][3] 表示以 A[1] 和 B[2] 结尾的公共子数组长度。 状态转移方程 如果 A[i-1] == B[j-1] ，则 dp[i][j] = dp[i-1][j-1] + 1 。 如果 A[i-1] != B[j-1] ，则 dp[i][j] = 0 （因为连续性要求，不匹配时长度重置为 0）。 转移方程： \[ dp[ i][ j ] = \begin{cases} dp[ i-1][ j-1] + 1, & \text{if } A[ i-1] = B[ j-1 ] \\ 0, & \text{otherwise} \end{cases} \] 初始化 当 i = 0 或 j = 0 时，表示一个数组为空， dp[0][j] = 0 ， dp[i][0] = 0 。 计算顺序与记录最大值 按 i 从 1 到 m ， j 从 1 到 n 的顺序计算 dp[i][j] 。 在计算过程中，用变量 max_len 记录所有 dp[i][j] 的最大值。 示例演算 以 A = [1,2,3,2,1] ， B = [3,2,1,4,7] 为例： 初始化 dp 为 5×5 的零矩阵。 当 i=3, j=1 ： A[2]=3 和 B[0]=3 匹配， dp[3][1] = dp[2][0] + 1 = 1 。 当 i=4, j=2 ： A[3]=2 和 B[1]=2 匹配， dp[4][2] = dp[3][1] + 1 = 2 。 当 i=5, j=3 ： A[4]=1 和 B[2]=1 匹配， dp[5][3] = dp[4][2] + 1 = 3 。 最终 max_len = 3 。 复杂度分析 时间复杂度：O(m × n)，空间复杂度：O(m × n)。 可优化空间至 O(min(m, n))（仅保留上一行或上一列）。 关键点总结 利用连续性简化状态转移：仅当当前字符匹配时继承前续状态。 通过遍历过程记录最大值，而非直接取 dp[m][n] 。 通过以上步骤，即可高效求解两个数组的最长公共子数组问题。