文章作者：Tyan
博客：noahsnail.com ?|? CSDN ?|? 簡書
1. Description
Maximum Length of Repeated Subarray
2. Solution
解析：求兩個(gè)數(shù)組的最長連續(xù)子序列厅贪，典型的動(dòng)態(tài)規(guī)劃問題堤器，動(dòng)態(tài)規(guī)劃問題最主要的就是找到狀態(tài)轉(zhuǎn)移方程田柔，確定狀態(tài)轉(zhuǎn)移方程之前要確定狀態(tài)戏蔑。通過兩層循環(huán)括儒，可以遍歷兩個(gè)數(shù)組所有的可能組合情況峰髓，dp[i][j]即第一個(gè)數(shù)組的前i個(gè)元素和第二個(gè)數(shù)組的前j個(gè)元素的最長連續(xù)子序列長度。初始狀態(tài)，所有的最長子序列長度都為0雾狈。循環(huán)開始，如果nums1[i]=nums2[j]抵皱，則最長子序列長度應(yīng)+1善榛，而總長度又取決于之前的dp[i-1][j-1]，如果nums1[i-1]=nums2[j-1]呻畸，則總長度+1移盆，如果nums1[i-1] != nums2[j-1]，則dp[i-1][j-1]=0伤为，dp[i][j]=1咒循，這兩種情況的狀態(tài)轉(zhuǎn)移方程都為dp[i][j] = dp[i-1][j-1] + 1据途，因?yàn)槌跏紶顟B(tài)設(shè)置時(shí)已經(jīng)將dp[i-1][j-1]設(shè)為了0。由于dp[1][1] = dp[0][0]+1叙甸，因此創(chuàng)建初始狀態(tài)矩陣時(shí)長度和寬度都要加1颖医。最后，從所有可能情況中找到最長的連續(xù)子序列長度裆蒸。
- Version 1
class Solution:
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
m = len(nums1)
n = len(nums2)
dp = [[0] * (n+1) for i in range(m+1)]
for i in range(m):
for j in range(n):
if nums1[i] == nums2[j]:
dp[i][j] = dp[i-1][j-1] + 1
return max(max(row) for row in dp)
