leetcode动态规划（二十六）-最长重复子数组

题目

718.最长重复子数组

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

示例 1：

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

示例 2：

输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出：5

思路

1.确定dp数组（dp table）以及下标的含义

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

2.确定递推公式

需做判断，如果nums[i-1]=nums[j-1]，那就dp[i][j] = dp[i-1][j-1]+1

根据递推公式可以看出，遍历i 和 j 要从1开始！

3.dp数组如何初始化

根据dp[i][j]的定义，dp[i][0] 和dp[0][j]其实都是没有意义的！

但dp[i][0] 和dp[0][j]要初始值，因为 为了方便递归公式dp[i][j] = dp[i - 1][j - 1] + 1;

所以dp[i][0] 和dp[0][j]初始化为0。

4.确定遍历顺序

由递推公式可得需从前向后遍历

5.打印dp

代码

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        n1 = len(nums1)
        n2 = len(nums2)
        if n1 == n2 and nums1 == nums2:
            return n1
        dp = [[0]*(n2+1) for _ in range(n1+1)] #需注意这里n1和n2哪个是行，哪个是列，混淆的花下面的循环将会出各种问题
        result = 0
        for i in range(1,n1+1):
            for j in range(1,n2+1):
                if nums1[i-1] == nums2[j-1]:
                    dp[i][j] = dp[i-1][j-1]+1

                if dp[i][j]>result:
                    result = dp[i][j]
        return result