day56 动态规划part13 代码随想录算法训练营 718. 最长重复子数组

题目：718. 最长重复子数组

我的感悟：

• 有难度，不好想。

理解难点：

• 二维DP，记住那个图：
• ===============
• 
• 

听课笔记：

我的代码：

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        # 初始化
        # 假设内层是nums1,n,j，外层是nums2,m,i
        n = len(nums1)  # 内
        m = len(nums2)  # 外
        dp = [[0]*(n+1) for _ in range(m+1)]
        res = 0
        for i in range(m):  # 外
            for j in range(n):  # 内
                if nums1[j] == nums2[i]:
                    dp[i+1][j+1] = dp[i][j] + 1
                    res = max(res,dp[i+1][j+1])
        return res

通过截图：

老师代码：

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        # 创建一个二维数组 dp，用于存储最长公共子数组的长度
        dp = [[0] * (len(nums2) + 1) for _ in range(len(nums1) + 1)]
        # 记录最长公共子数组的长度
        result = 0

        # 遍历数组 nums1
        for i in range(1, len(nums1) + 1):
            # 遍历数组 nums2
            for j in range(1, len(nums2) + 1):
                # 如果 nums1[i-1] 和 nums2[j-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

扩展写法：

资料：

leetcode - 【狗大王】题解