区间动态规划例题：最长重复子数组问题 题目描述 给定两个整数数组 nums1 和 nums2 （长度分别为 m 和 n ），要求找到两个数组中 连续 的公共子数组的 最大长度 。例如： 输入： nums1 = [1,2,3,2,1] , nums2 = [3,2,1,4,7] 输出： 3 （因为最长公共连续子数组是 [3,2,1] ，长度为 3）。 解题思路 问题分析 本题要求的是 连续子数组 的公共部分，而非不连续的子序列（如最长公共子序列问题）。 关键观察：如果 nums1[i] 和 nums2[j] 是公共子数组的结尾元素，那么公共子数组的长度取决于 nums1[i-1] 和 nums2[j-1] 是否匹配。 定义状态 设 dp[i][j] 表示以 nums1[i-1] 和 nums2[j-1] 为结尾的最长公共子数组的长度（索引从 1 开始便于边界处理）。 为什么用 i-1 和 j-1 ？这是为了在 i=0 或 j=0 时表示空数组，避免负索引。 状态转移方程 如果 nums1[i-1] == nums2[j-1] ，则 dp[i][j] = dp[i-1][j-1] + 1 。 如果 nums1[i-1] != nums2[j-1] ，则 dp[i][j] = 0 （因为连续子数组在此断开）。 注意：公共子数组必须连续，因此不匹配时直接归零。 初始化 当 i=0 或 j=0 时，表示一个数组为空， dp[0][j] = 0 ， dp[i][0] = 0 。 计算过程 遍历 i 从 1 到 m ， j 从 1 到 n ，根据状态转移方程更新 dp[i][j] 。 同时记录所有 dp[i][j] 的最大值，即为答案。 复杂度优化 时间复杂度：O(m* n)，空间复杂度可优化至 O(n)（仅保留上一行 dp 值）。 示例演示 以 nums1 = [1,2,3,2,1] , nums2 = [3,2,1,4,7] 为例： 构建 dp 表（尺寸 6×6，因包含空数组行/列）： 当 i=3 , j=1 ： nums1[2]=3 与 nums2[0]=3 匹配， dp[3][1] = dp[2][0] + 1 = 1 。 当 i=4 , j=2 ： nums1[3]=2 与 nums2[1]=2 匹配， dp[4][2] = dp[3][1] + 1 = 2 。 当 i=5 , j=3 ： nums1[4]=1 与 nums2[2]=1 匹配， dp[5][3] = dp[4][2] + 1 = 3 。 最终最大值为 3，对应子数组 [3,2,1] 。 关键点总结 区分“子数组”（连续）与“子序列”（可不连续）的状态转移差异。 通过 dp[i][j] 记录以特定位置结尾的公共子数组长度，避免重复计算。 实际代码中可通过滚动数组降低空间复杂度。