动态规划：力扣718. 最长重复子数组

1、题目描述：

2、题解：

状态定义： dp[i][j]：数组A的前i个字符和数组B的前j个字符公共子数组的的个数 状态转移方程： 如果A[i] == B[j],那么： dp[i][j] = dp[i-1][j-1]+1 初始化： 所有dp为0，dp[0][0]为0，解释：A的前0个字符和B的前0个字符的公共子数组的个数为0 比如： 对于示例：

[1,2,3,2,1] [3,2,1,4,7]

dp数组为：

3 2 1 4 7 [ [0, 0, 0, 0, 0, 0], 1 [0, 0, 0, 1, 0, 0], 2 [0, 0, 1, 0, 0, 0], 3 [0, 1, 0, 0, 0, 0], 2 [0, 0, 2, 0, 0, 0], 1 [0, 0, 0, 3, 0, 0]]

代码如下：

class Solution: def findLength(self, A: List[int], B: List[int]) -> int: #动态规划 res = 0 m,n = len(A),len(B) dp = [[0]*(n+1) for _ in range(m+1)] for i in range(1,m+1): for j in range(1,n+1): if A[i-1] == B[j-1]: dp[i][j] = dp[i-1][j-1] + 1 res = max(res,dp[i][j]) return res

3、复杂度分析：

时间复杂度：O(NM)，N、M分别是两个数组的长度 空间复杂度：O(NM)