最长公共子序列

双串问题的状态如何定义？

• 问题: 求两个字符串的最长公共子序列长度 (1143);
• 阶段: 按两个字符串的前缀长度划分;
• 状态: dp[i][j] 为 text1 前 i 个字符与 text2 前 j 个字符的最长公共子序列长度;
• 下标设计: 用 dp[0][*]、dp[*][0] 表示空串, 循环从 1 开始, 访问字符用 i-1、j-1;
• 初值: 空串与任何串的公共子序列长度为 0;
• 答案: dp[m][n];

转移方程如何写？

• 相同: 若 text1[i-1] === text2[j-1], 该字符一定可以进入公共子序列, dp[i][j] = dp[i-1][j-1] + 1;
• 不同: 两个末位字符至少舍弃一个, dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
• 复杂度: 时间 O(mn), 空间 O(mn);

const longestCommonSubsequence = (text1, text2) => {
  const m = text1.length;
  const n = text2.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
      else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
    }
  }
  return dp[m][n];
};

子序列和子数组的转移差在哪里？

• 问题对照: 最长公共子序列 (可不连续) 与最长重复子数组 (必须连续) (718);
• 子序列: 末位不同时仍可继承 max(dp[i-1][j], dp[i][j-1]), 信息跨过断点;
• 子数组: 末位不同时连续性破坏, 状态必须归零 dp[i][j] = 0;
• 子数组: 答案要额外维护 res = max(res, dp[i][j]), 因为最长匹配不一定在末尾;

const findLength = (nums1, nums2) => {
  const m = nums1.length;
  const n = nums2.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  let res = 0;
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (nums1[i - 1] === nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
      res = Math.max(res, dp[i][j]);
    }
  }
  return res;
};

• 记忆点: 连续要求 → 断点归零; 非连续 → 断点继承;