LeetCode-718. 最长重复子数组

题目

给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

示例：

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

提示：

1 <= len(A), len(B) <= 1000 0 <= A[i], B[i] < 100

思路【动态规划】：

第 1 步：定义状态

dp[i][j] 的含义是：对于 A[1..i] 和 B[1..j]，它们的 最长重复子数组 长度是 dp[i][j]，假设索引是从 1 开始的。

第 2 步：考虑状态转移方程 状态转移说简单些就是做选择，要求 A 和B的最长重复子数组，不妨称这个子数组为 lrs（Longest repeating subarray ）。那么对于 A 和 B 中的每个元素，有什么选择？很简单，两种选择，要么在 lrs 中，要么不在。

应该如何选择呢？

用两个指针 i 和 j 从后往前遍历 A 和 B，如果 A[i]==B[j]，那么这个字符一定在 lrs 中；否则的话，A[i] 和 B[j] 这两个元素至少有一个不在 lrs 中，。

对于第一种情况，找到一个 lrs 中的字符，同时将 i j 向前移动一位，并给 lrs 的长度加一；对于后者，则dp[i][j]置为0，重新计数。

因此，dp[i] [j]的状态转移方程是： $$dp[i][j]=\{\begin{array}{l}1+dp[i-1][j-1]，A[i-1]==B[j-1]\\ 0，其他\end{array}$$ 第 3 步：考虑初始化

我们专门让索引为 0 的行和列表示空串，dp[0][..] 和 dp[..][0] 都应该初始化为 0，这就是 base case。

比如说，按照刚才 dp 数组的定义，dp[0][3]=0 的含义是：对于元素 null和 2，其 LRS 的长度为 0。因为有一个元素是空，它们的最长重复元素的长度显然应该是 0。

第 4 步：考虑输出 这种定义之下，这里要注意，不能返回最后一个状态值；状态数组 dp 的最大值才是最后要输出的值。

代码实现：

class Solution { public int findLength(int[] A, int[] B) { int len1 = A.length; int len2 = B.length; int[][] dp = new int[len1 + 1][len2 + 1]; int ans = 0; for (int i = 1; i <= len1; i++) { for (int j = 1; j <= len2; j++) { if (A[i-1] == B[j-1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = 0; } ans = Math.max(ans,dp[i][j]); } } return ans; } }

复杂度分析：

时间复杂度：$O(len1\ast len2)$。空间复杂度：$O(len1\ast len2)$。