题解 | #最长公共子数组#

利用二维 dp 求解，dp[i][j] 表示数组 A[i] 和 B[j] 内的最长公共子数组的长度 转移状态方程为: dp[i][j] = dp[i - 1][j - 1] + 1 A[i] = B[j] 因为公共子数组是连续的子数组,所以当 A[i] != B[j] 时的情况不用考虑 dp 的初始长度设置为 dp = [[len(B) + 1] len(A) + 1], 这样在遍历时将初值代入 设置 res 表示最终结果,在遍历中更新该值

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param A int整型一维数组 
# @param B int整型一维数组 
# @return int整型
#
class Solution:
    def longestCommonSubarry(self , A: List[int], B: List[int]) -> int:
        # write code here
        dp = [[0 for _ in range(len(B) + 1)] for _ in range(len(A) + 1)]
        res = 0
        for i in range(1, len(A) + 1):
            for j in range(1, len(B) + 1):
                if A[i - 1] == B[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                    res = max(dp[i][j], res)
        return res