文章目录

leetcode718. 最长重复子数组方法：动态规划思路：代码：结果：

leetcode718. 最长重复子数组

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

示例 1:

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

说明:

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

---

方法：动态规划

思路：

最暴力的方法就是枚举AB所有的子数组进行对比，这样的话，AB分别枚举所有子数组需要O(N ^ 2)，那么总的时间复杂度需要O(N^4)，肯定不可以。肯定是用动态规划来降低重复计算。

我们来找在哪里可以用到动态规划，对于重复的子数组，可以发现，**如果这两个数组的前面一个数相等，那么重复的长度就可以加1。**不需要比对后面的，因为已经相等了，我们的大致思想就是，找到重复的部分，然后往前扩展，如果新扩展的两个数相等，那么重复部分长度就增加了。

我们使用dp(i,j)来表示A[i:]和B[j:]两个子数组的相同的前缀的长度。

那么状态转移方程为： $$dp[i][j]=\{\begin{array}{llc}0& if& A[i]\ne B[j]\\ dp[i+1][j+1]+1& if& A[i]=B[j]\end{array}$$ 即，如果A[i]和B[j]相等，那么重复前缀的长度就在之前的基础上加一，如果不相等，那么就归零。

下面考虑边界条件，根据状态转移方程，dp(i,j)与右下角的dp有关，因此需要先将最后一行和最后一列的dp填写好。对于最后一行，就表示A[-1]和B中所有值是否相等，相等为1；对于最后一列，就是B[-1]和A中所有值是否相等，相等为1。

我们填写dp的同时维护一个变量保存dp数组中的最大值，最后返回这个最大值即为最长的重复数组长度。

代码：

class Solution: def findLength(self, A: List[int], B: List[int]) -> int: m = len(A) n = len(B) ans = 0 #初始化dp，dp[i][j]表示A[i:]与B[j:]的相同前缀的长度 dp = [[0 for _ in range(n)] for _ in range(m)] #初始化最后一行与最后一列 for i in range(n): if B[i] == A[m-1]: dp[m-1][i] = 1 ans = 1 for j in range(m): if A[j] == B[n-1]: dp[j][n-1] = 1 ans = 1 #如果只有一行或一列 if m == 1 or n == 1: return ans #完成dp的填写，状态转移方程为 #dp[i][j] = 0(A[i]!=B[j]) 或 dp[i+1][j+1] + 1 (else) for i in range(m-2,-1,-1): for j in range(n-2,-1,-1): if A[i] == B[j]: dp[i][j] = dp[i+1][j+1] + 1 ans = max(ans,dp[i][j]) return ans

结果：