2020-07-01-每日一题
程序员文章站
2022-11-30 13:34:25
更多python分类刷题题解代码:请参考github,博客, 知乎718. 最长重复子数组(medium)https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/# 动态规划# dp[i][j]表示以i为结束元素的A和以j为结束的B,的最长的公共子数组的长度# 状态转移方程# if A[i] == B[j] 则, dp[i][j] = dp[i-1][j-1] + 1# else: dp[i][j] =...
更多python分类刷题题解代码:请参考github,博客, 知乎
718. 最长重复子数组(medium)
https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/
# 动态规划
# dp[i][j]表示以i为结束元素的A和以j为结束的B,的最长的公共子数组的长度
# 状态转移方程
# if A[i] == B[j] 则, dp[i][j] = dp[i-1][j-1] + 1
# else: dp[i][j] = 0
# 边界条件:
# dp[0][i] = 1 if A[0] == B[i]
# dp[i][0] = 1 if A[i] == B[0]
class Solution:
def findLength(self, A: List[int], B: List[int]) -> int:
if not A: return 0
l = len(A)
dp = [[0]*l for _ in range(l)]
res = 0
for i in range(l):
if A[0] == B[i]:
dp[0][i] = 1
res = max(dp[0][i], res)
if A[i] == B[0]:
dp[i][0] = 1
res = max(dp[i][0], res)
for i in range(1, l):
for j in range(1, l):
if A[i] == B[j]:
dp[i][j] = dp[i-1][j-1] + 1
res = max(dp[i][j], res)
else:
dp[i][j] = 0
# print(dp)
return res
更多python分类刷题题解代码:请参考github,博客, 知乎
本文地址:https://blog.csdn.net/lxztju/article/details/107134813
上一篇: lambda常用操作