718-最长重复子数组.md

题目描述

最长重复子数组

给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

示例 1：

• 输入：
  • A: [1,2,3,2,1]
  • B: [3,2,1,4,7]
• 输出：3
• 解释：
• 长度最长的公共子数组是 [3, 2, 1] 。

分类

中等 动态规划

思路

思路 1

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findLength = function (nums1, nums2) {
  // dp[i][j] 代表 nums1[i]  nums[j]相同的 截至的 长度
  const dp = Array.from({ length: nums1.length }, () =>
    new Array(nums2.length).fill(0)
  );
  let max = 0;
  for (let i = 0; i < nums1.length; i++) {
    for (let j = 0; j < nums2.length; j++) {
      if (nums1[i] === nums2[j]) {
        if (!i || !j) {
          dp[i][j] = 1;
        } else {
          dp[i][j] = dp[i - 1][j - 1] + 1;
        }
        max = Math.max(dp[i][j], max);
      }
    }
  }
  return max;
};

• 问题分析
  • 我要求什么？这个值能够直接通过递推求出来吗？
    • 求以nums1[i],nums2[j]为截止，之前公共的、长度最长的子数组的长度。如果使用dp[i][j]储存这个值(dp[i][j]是储存nums1[i]、nums2[j]前的公共的、长度最长的子数组的长度)，那么i,j能够通过dp[i - 1]``dp[j - 1]推导，因为dp[i - 1][j - 1]是已知且如果可以推导，则dp[i][j] = dp[i - 1][j - 1] + 1
  • 初始值是什么呢，能够由前几个结果递推呢？
    • 默认dp[i][j]的元素为0，因为未知情况下不知道是否有公共数组。
  • 按照递推的逻辑，循环的顺序应该是怎么样子才能进行递推？
    • 只有当nums1[i]和nums2[j]相同时，才能够递推，否则就是为0，不用进行推导。根据递推的规则易知i j都应该是递增的，否则推导是没有前向依赖的。