最长公共子序列 LCS （Longest Common Subsequence）被广泛用于生产中，如 git 中对比 commit 串等，本文简述一下动态规划解决 LCS 算法的问题。
子序列定义 Link to heading
对于某个序列 $l = [a_1, a_2, …, a_n]$ ，称序列 $l’ = [a_{i_1}, a_{i_2}, …, a_{i_k}]$ ，其中 $i_1 < i_2 < … < i_k$ 为序列 $l$ 的子序列。注意这个子序列指需要保证有序，不需要保证连续。
衍生描述：不相交的线。
LCS 问题算法 Link to heading
使用动态规划解决。定义 $dp[i][j]$ 描述序列 1 前 i 个元素和序列 j 前 j 个元素的最长公共子序列。
-
当 $i = 0$ 或 $j = 0$ 时，易得 $dp[i][j] = 0$；
-
当 $i > 0$ 且 $j > 0$ 时：
-
若 $l_1[i] = l_2[j]$，此时必然有 $dp[i][j] = dp[i-1][j-1] + 1$。
-
若 $l_1[i] \neq l_2[j]$，此时有 $dp[i][j] = max(dp[i-1][j], dp[i][j-1])$。
-
代码实现 Link to heading
1def lcs(l1, l2):
2 dp = [[0] * (len(l2) + 1) for _ in range(len(l1) + 1)]
3 for i in range(1, len(l1) + 1):
4 for j in range(1, len(l2) + 1):
5 if l1[i - 1] == l2[j - 1]:
6 dp[i][j] = dp[i - 1][j - 1] + 1
7 else:
8 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
9 return dp[-1][-1]
1function lcs(l1: any[], l2: any[]) {
2 const dp = [...Array(l1.length+1)].map(() => Array(l2.length+1).fill(0))
3 for (let i = 0; i < l1.length; i++) {
4 for (let j = 0; j < l2.length; j++) {
5 if (l1[i] === l2[j]) {
6 dp[i+1][j+1] = dp[i][j] + 1
7 } else {
8 dp[i+1][j+1] = Math.max(dp[i][j+1], dp[i+1][j])
9 }
10 }
11 }
12
13 return dp.at(-1).at(-1)
14}