718 Maximum Length of Repeated Subarray
https://leetcode.com/problems/maximum-length-of-repeated-subarray/
solution
动态规划
这里是最长重复子数组,和最长公共子序列的不同在于需要子数组是连续的。
子数组的dp含义是: 以下标i - 1为结尾的A,和以下标j - 1为结尾的B,最长重复子数组长度为dp[i][j]
公共子序列的dp含义是: 长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]
为什么是以...结尾的,否则断开之后,再有相同值的就会dp值会继续累加上去。因此要求连续的含义需要以...结尾的,不要求连续则是长度为...的
时间复杂度:O() 空间复杂度:O()
Last updated