子序列 DP：LIS 与 LCS

一、面试常考点

1. LIS 与 LCS 区别

LIS 单序列严格递增；LCS 双序列最长公共子序列。

2. LCS 标准转移

字符相等看左上角 +1，不等看上/左最大值。

二、细节介绍

1. LIS（O(n^2)）

dp[i] 表示以 i 结尾的 LIS 长度。

2. LCS

dp[i][j] 表示 s1[0..i-1] 和 s2[0..j-1] 的 LCS 长度。

三、示例代码

function lcs(s1, s2) {
  const n = s1.length
  const m = s2.length
  const dp = Array.from({ length: n + 1 }, () => Array(m + 1).fill(0))

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
      if (s1[i - 1] === s2[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[n][m]
}

四、常用应用场景

1. 文本比对

差异分析、版本比较。

2. 推荐系统序列建模

用户行为序列相似度比较。