718. Maximum Length of Repeated Subarray

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

solution

• 动态规划

  • 最长重复子数组，和最长公共子序列的不同在于需要子数组是连续的

  • 子数组的dp含义是: 以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]

  • 公共子序列的dp含义是: 长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]

  • 为什么是以...结尾的，否则断开之后，再有相同值的就会dp值会继续累加上去。因此要求连续的含义需要以...结尾的，不要求连续则是长度为...的

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        # dp[i][j]: 以i-1为结尾的nums1和以nums2为结尾的nums2的最长重复子序列
        dp = [[0] * (len(nums2) + 1) for _ in range(len(nums1) + 1)]
        res = 0
        for i in range(1, len(nums1)+1):
            for j in range(1, len(nums2)+1):
                if nums1[i-1] == nums2[j-1]:  # 这里一开始的判断条件写错了
                    dp[i][j] = dp[i-1][j-1] + 1
                    if dp[i][j] > res:
                        res = dp[i][j]
        return res

时间复杂度：O() 空间复杂度：O()