LeetCode 718. 最长重复子数组

题目

给两个整数数组 nums1 和 nums2 ，返回两个数组中公共的 、长度最长的子数组的长度 。

例：
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。

方法：动态规划

• dp[i][j] 表示以 i-1 为结尾的数组 nums1 和以 j-1 为结尾的数组 nums2 的最长重复子数组
• result 表示此时（最终）最长重复子数组的长度
• 外层循环是对数组 nums1 的循环，内层循环是对数组 nums2 的循环。若此时的位于不同数组的两个数字相等，那么记录此时重复子数组的长度 dp[i-1][j-1] + 1。通过对各个重复子数组长度的对比，最终得到最长重复子数组的长度

class Solution(object):
    def findLength(self, nums1, nums2):
        dp = [[0] * (len(nums2)+1) for row in range(len(nums1)+1)]
        result = 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
                result = max(result, dp[i][j])
        return result

参考

代码相关：https://programmercarl.com/0718.%E6%9C%80%E9%95%BF%E9%87%8D%E5%A4%8D%E5%AD%90%E6%95%B0%E7%BB%84.html