模版题-动态规划-最长重复子数组( 匹配类问题的思考方式 )
- 版权声明：本站原创文章，于2026-06-02，由 管理员 发表。
- 转载请注明： 模版题-动态规划-最长重复子数组( 匹配类问题的思考方式 ) | CodeGarden
```python
class Solution:
# 给两个整数数组 nums1 和 nums2 ，返回两个数组中公共的、长度最长的子数组的长度。
# 1 <= nums1.length, nums2.length <= 1000
# 0 <= nums1[i], nums2[i] <= 100
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
# 子数组,其实就是连续子序列。
# 暴力:
"""
ans = 0
for nums1的起始下标:
for nums2的起始下标:
# 起始坐标开始两者相同的元素个数
count = 0
while nums1[ x ] == nums2[ y ]: count += 1
if count > ans: ans = count
return ans
"""
n1, n2 = len( nums1 ), len( nums2 )
if n1 == 0 or n2 == 0: return 0
# 动态规划优化: 利用二维数组记录两两元素的比较结果
# dp[ i ][ j ]表示:
# - 以nums1[ i - 1 ]结尾的子数组
# - 以nums2[ j - 1 ]结尾的子数组
# 的公共的最长子数组长度
# ---> dp之所以定义为i-1结尾和j-1结尾主要是为了方便初始化
# ---> 若dp定义为i结尾和j结尾 需要额外处理一下初始化
dp = [ [ 0 for _ in range( n2 + 1 ) ] for _ in range( n1 + 1 ) ]
ans = 0
for i in range( 1, n1 + 1 ):
for j in range( 1, n2 + 1 ):
# 若nums1[ i - 1 ] == nums[ j - 1 ]那么公共长度: dp[ i - 1 ][ j - 1 ] + 1
# 若nums1[ i - 1 ] != nums[ j - 1 ]那么: 公共子数组要求连续,一旦不相等就应该清零,不能继承。
if nums1[ i - 1 ] == nums2[ j - 1 ]: dp[ i ][ j ] = dp[ i - 1 ][ j - 1 ] + 1
if dp[ i ][ j ] > ans: ans = dp[ i ][ j ]
return ans
```