image.png

思路

概念理解:子序列和子数组(子串)

子序列默认不连续,子数组默认连续

分析

其实我还是没太搞懂,为什么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
image.png
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

  1. var findLength = function(nums1, nums2) {
  2. // dp的定义是,以下标i - 1为结尾的A,和以下标j - 1为结尾的B,最长重复子数组长度为dp[i][j]。
  3. let dp =new Array(nums1.length+1).fill(0).map(()=>new Array(nums2.length+1).fill(0))
  4. let result =0
  5. for(let i=1;i<=nums1.length;i++){
  6. for(let j=1;j<=nums2.length;j++){
  7. if(nums1[i-1]===nums2[j-1]){
  8. dp[i][j]=dp[i-1][j-1]+1
  9. }
  10. result =Math.max(result,dp[i][j])
  11. }
  12. }
  13. return result
  14. };