给两个整数数组 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
自我解答(动态规划)
这题太难了，看了提示后也想了好久才想出来。
尝试 “最大子序列和” 的思路，将最优问题转化成
在A列表中，求解出所有以 i 开头/结尾的最大重复子数组长度
记为 f(i), 然后尝试寻找 f(i) 与 f(i+1) 的关系，可这样是没有意义的，因为这个列表每个位置 i,
可以和另一个列表的任何元素进行匹配，这就意味着 f(i) 与 f(i+1) 没有关系，仅仅考虑单个列表是不够的。
由此可见，似乎不可避免地需要考虑所有组合数，可是这样的话，就不可避免造成时间复杂度 O(n*m),
这样真的是可接受的吗？为此，我想了很久其他的 O(n) 方案，没有结果。
如果真的需要考虑所有组合数，那又怎么找最优子结构呢？怎么去勾画最优子问题呢？
设 f(i, j): 以 A[i], B[j] 开头的最长重复子数组长度
发现 最优子结构：
if A[i] == B[j]:
f(i, j) = 1 + f(i+1, j+1)
else:
f(i, j) = 0
因此得出方案一：
1、设计出递归函数 f(i, j)
2、为了覆盖到所有情况，使用两层循环遍历所有的(i, j)组合
3、由于递归函数的存在，循环遍历过程中会出现计算过的f(i, j)组合，因此加入备忘机制
由此可设计出 自顶向下带备忘的 动态规划算法。可惜超时了。
class Solution:
def findLength(self, A: List[int], B: List[int]) -> int:
self.A, self.B = A, B
self.lena, self.lenb = len(A), len(B)
self.cache = {}
self.maxres = 0
for j in range(0, self.lenb):
self.find_len(0, j)
for i in range(1, self.lena):
self.find_len(i, 0)
return self.maxres
def find_len(self, i, j):
if i == self.lena or j == self.lenb:
return 0
if (i, j) in self.cache:
return self.cache[(i, j)]
res = 0
next_len = self.find_len(i + 1, j + 1)
if self.A[i] == self.B[j]:
res = 1 + next_len
if res > self.maxres:
self.maxres = res
self.cache[(i, j)] = res
return res
由于此题的本身就比较复杂，“自顶向下带备忘法” 在此处时间开销过大了(递归栈维护，重复遍历，缓存维护)。
我以为最优子结构找错了，为此又陷入了久久的沉思....
最终发现力扣报超时，是因为超过了python的最大递归深度，看来改成 “自底向上法” 就可以了。
自底向上法是指：将所有子问题按规模从小到大排列，从最小子问题开始，确保在求解每个子问题时，所依赖的前置
子问题都已求解，并且确保每个子问题都只求解一次，不需要缓存备忘。
同样的，最优子问题刻画为:
设 f(i, j): 以 A[i], B[j] 开头的最长重复子数组长度
此题 f(i, j) 的所有组合数就是两个列表两两组合数，其实就是个矩阵, 我们要做的事：
1、矩阵中所有元素只访问一次，即在访问过程中求解 f(i, j)
2、将 f(i, j) 按规模从小到大排列，确保在求解 f(i, j)时, f(i+1, j+1) 已求解
因此, 假设两个列表的长度分别为 N 和 M，可以从 f(N-1, M-1)开始求解， 求解过程：(1 表示已求解)
0, 0, 0, 0 0, 0, 0, 0 0, 1, 0, 0
0, 0, 0, 0 -> 0, 0, 1, 0 -> 0, 0, 1, 0
0, 0, 0, 1 0, 0, 0, 1 0, 0, 0, 1
由此，得到了 方案二:
完成上半部分后，再完成下半部分就可以了
执行结果：
执行用时：3288 ms, 在所有 Python3 提交中击败了 85.24% 的用户
内存消耗：13.5 MB, 在所有 Python3 提交中击败了 89.87% 的用户
class Solution2:
def findLength(self, A: List[int], B: List[int]) -> int:
self.A, self.B, lena, lenb = A, B, len(A), len(B)
self.maxlength = 0
for i in range(lena - 1, -1, -1):
self.get_length(i, lenb - 1)
for j in range(lenb - 2, -1, -1):
self.get_length(lena - 1, j)
return self.maxlength
def get_length(self, i: int, j: int) -> None:
dp = 0
while i >= 0 and j >= 0:
if self.A[i] == self.B[j]:
dp += 1
if dp > self.maxlength:
self.maxlength = dp
else:
dp = 0
i -= 1
j -= 1
原题链接：https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray