题目
难度：★★★☆☆
类型：数组
方法：动态规划
力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录
给两个整数数组 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和B的长度分别为m和n，定义数组dp，维度为m×n，dp[i][j]表示A[:i+1]子数组和B[:j+1]子数组中的最长公共子数组的长度。
【初始状态】
最开始的情况，根据题目逻辑，将所有数组中的元素填充零。
【状态转移】
状态转移条件：遍历AB数组中每个元素，当遇到A[i]==B[j]时执行：
状态转移方程：dp[i][j]=dp[i-1][j-1]+1
解释：A[:i+1]子数组和B[:j+1]子数组的结尾元素A[i]和B[j]相等时，相当于可以扩展它们的公共子数组的长度。
【最终状态】
统计dp数组中最大值返回即可。
class Solution:
def findLength(self, A, B) -> int:
n, m = len(A), len(B)
dp = [[0 for i in range(m)] for j in range(n)]
ans = 0
for i in range(n):
for j in range(m):
if A[i] == B[j]:
dp[i][j] = dp[i - 1][j - 1] + 1 if i > 0 and j > 0 else 1
if dp[i][j] > ans:
ans = dp[i][j]
# print(dp)
return ans
如有疑问或建议，欢迎评论区留言~
有关更多力扣中等题的python解决方案，请移步力扣中等题解析
