leetcode718.最长重复子数组

方法是用的官方的方法，练得还不多，只能想到暴力O(n^3)复杂度的算法，用脚趾头想都知道过不了。 dp动态规划学是学了，但是应用起来还是想不明白，有题练练挺好。 执行用时： 3880 ms, 在所有 Python 提交中击败了15.00%的用户 内存消耗： 34.5 MB, 在所有 Python 提交中击败了100.00%的用户

算法描述

动态规划解法：优化最长公共前缀的比较 if A[i]==B[i]: A[i:]与B[i:]的最长公共前缀为A[i+1:]与B[i+1:]的最长公共前缀+1 else: A[i:]与B[i:]的最长公共前缀=0 填表：dp[i][j]表示A[i:]与B[i:]的最长公共前缀，return max(dp[i][j]) if A[i]==B[i]: dp[i][j]=dp[i+1][j+1]+1 else: dp[i][j]=0

源代码

class Solution(object): def findLength(self, A, B): """ :type A: List[int] :type B: List[int] :rtype: int """ n = len(A) m = len(B) ans = 0 dp = [[0 for i in range(m+1)] for j in range(n+1)] # 二维数组生成法，不用这个就要用numpy，长度定位m+1和n+1就可以免去考虑最后一个元素的麻烦 for i in range(m - 1, -1, -1): for j in range(n - 1, -1, -1): dp[i][j] = dp[i + 1][j + 1] + 1 if A[i] == B[j] else 0 ans = max(ans, dp[i][j]) return ans