文章作者：Tyan
博客：noahsnail.com | CSDN | 简书
1. Description
Maximum Length of Repeated Subarray
2. Solution
解析：求两个数组的最长连续子序列，典型的动态规划问题，动态规划问题最主要的就是找到状态转移方程，确定状态转移方程之前要确定状态。通过两层循环，可以遍历两个数组所有的可能组合情况，dp[i][j]即第一个数组的前i个元素和第二个数组的前j个元素的最长连续子序列长度。初始状态，所有的最长子序列长度都为0。循环开始，如果nums1[i]=nums2[j]，则最长子序列长度应+1，而总长度又取决于之前的dp[i-1][j-1]，如果nums1[i-1]=nums2[j-1]，则总长度+1，如果nums1[i-1] != nums2[j-1]，则dp[i-1][j-1]=0，dp[i][j]=1，这两种情况的状态转移方程都为dp[i][j] = dp[i-1][j-1] + 1，因为初始状态设置时已经将dp[i-1][j-1]设为了0。由于dp[1][1] = dp[0][0]+1，因此创建初始状态矩阵时长度和宽度都要加1。最后，从所有可能情况中找到最长的连续子序列长度。
- Version 1
class Solution:
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
m = len(nums1)
n = len(nums2)
dp = [[0] * (n+1) for i in range(m+1)]
for i in range(m):
for j in range(n):
if nums1[i] == nums2[j]:
dp[i][j] = dp[i-1][j-1] + 1
return max(max(row) for row in dp)
