2020-07-01-每日一题

更多python分类刷题题解代码：请参考github,博客, 知乎

718. 最长重复子数组（medium）

https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/

# 动态规划
# dp[i][j]表示以i为结束元素的A和以j为结束的B，的最长的公共子数组的长度
# 状态转移方程
#   if A[i] == B[j] 则， dp[i][j] = dp[i-1][j-1] + 1
#   else: dp[i][j] = 0
# 边界条件：
#     dp[0][i] = 1 if A[0] == B[i]
#     dp[i][0] = 1 if A[i] == B[0]

class Solution:
    def findLength(self, A: List[int], B: List[int]) -> int:
        if not A: return 0
        l = len(A)
        dp = [[0]*l for _ in range(l)]
        res = 0
        for i in range(l):
            if A[0] == B[i]:
                dp[0][i] = 1
                res = max(dp[0][i], res)
            if A[i] == B[0]:
                dp[i][0] = 1
                res = max(dp[i][0], res)
        
        for i in range(1, l):
            for j in range(1, l):
                if A[i] == B[j]:
                    dp[i][j] = dp[i-1][j-1] + 1
                    res = max(dp[i][j], res)
                else:
                    dp[i][j] = 0
        # print(dp)
        return res

更多python分类刷题题解代码：请参考github,博客, 知乎

更多技术文章请点击查看

本文地址：https://blog.csdn.net/lxztju/article/details/107134813