题目 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
思路
- 动态规划
- 公式:dp[i][j] = dp[i-1][j-1] + 1
只有当nums[i-1] == nums[j-1]时才会运行公式 - 一定要自己画出来矩阵走走就特别清晰了
代码
class Solution:
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
row = len(nums1)+1
col = len(nums2)+1
dp = [[0]*col for i in range(row)]
res = 0
for i in range(1, row):
for j in range(1, col):
if nums1[i-1] == nums2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
res = max(res, max(dp[i]))
return res
标签:718,res,最长,nums2,数组,nums1,dp
From: https://www.cnblogs.com/edkong/p/17216219.html