思路
概念理解:子序列和子数组(子串)
分析
其实我还是没太搞懂,为什么dp的定义是i-1和j-1呢
【想到一个解释,如果是下标i和下标j结尾,那么初始化比较麻烦把!】
dp[i][j] :以下标i - 1为结尾的A,和以下标j - 1为结尾的B,最长重复子数组长度为dp[i][j]。
当A[i - 1] 和B[j - 1]相等的时候,dp[i][j] = dp[i - 1][j - 1] + 1;
因为dp[0][j]和dp[i][0],表示另一个数组是空的,空的肯定没有重复子序列,所以初始化为0
m长度=5,n长度=5
当i=1,m=1-5,
nums1[i-1] =1,1,1,1,1
nums2[j-1] =3,2,1,4,7
当i=1,j=3时符合条件
dp[1][3] =dp[0][2] +1
var findLength = function(nums1, nums2) {
// dp的定义是,以下标i - 1为结尾的A,和以下标j - 1为结尾的B,最长重复子数组长度为dp[i][j]。
let dp =new Array(nums1.length+1).fill(0).map(()=>new Array(nums2.length+1).fill(0))
let result =0
for(let i=1;i<=nums1.length;i++){
for(let j=1;j<=nums2.length;j++){
if(nums1[i-1]===nums2[j-1]){
dp[i][j]=dp[i-1][j-1]+1
}
result =Math.max(result,dp[i][j])
}
}
return result
};