最长公共子序列（LCS - Longest Common Subsequence）
📌 定义
最长公共子序列（LCS）是指在两个序列中都出现且相对顺序一致的最长子序列。注意是子序列（不要求连续），不是子串。
序列1: ABCDGH
序列2: AEDFHR
LCS: ADH (长度为3)
核心思路
使用动态规划求解，定义状态：
dp[i][j]表示s1[0...i-1]和s2[0...j-1]的最长公共子序列长度
💡 状态转移方程
如果 s1[i-1] == s2[j-1]，两个序列的最后一个字符可以同时纳入答案：
dp[i][j] = dp[i-1][j-1] + 1
如果两个字符不同，最优解至少要舍弃其中一个字符：
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
初始状态是 dp[0][j] = 0、dp[i][0] = 0，因为空序列和任何序列的公共子序列长度都是 0。
为什么只看两个方向
当末尾字符不同，它们不可能同时出现在同一条公共子序列的末尾，所以最优解必然来自“跳过
s1[i-1]”或“跳过s2[j-1]”两种情况。
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(m×n) | m和n分别是两个序列的长度 |
| 空间复杂度 | O(m×n) | 需要二维DP数组 |
| 优化空间 | O(min(m,n)) | 滚动数组优化 |
Go 代码
Go 实现
package main
import "fmt"
func longestCommonSubsequence(text1, text2 string) int {
m, n := len(text1), len(text2)
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
}
for i := 1; i <= m; i++ {
for 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] = max(dp[i-1][j], dp[i][j-1])
}
}
}
return dp[m][n]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func main() {
text1 := "ABCDGH"
text2 := "AEDFHR"
fmt.Printf("'%s' 和 '%s' 的LCS长度: %d\n",
text1, text2, longestCommonSubsequence(text1, text2))
}🎯 DP表格示例
text1 = "ABCDGH"
text2 = "AEDFHR"
"" A E D F H R
"" 0 0 0 0 0 0 0
A 0 1 1 1 1 1 1
B 0 1 1 1 1 1 1
C 0 1 1 1 1 1 1
D 0 1 1 2 2 2 2
G 0 1 1 2 2 2 2
H 0 1 1 2 2 3 3
dp[6][6] = 3 (答案)
LCS = "ADH"
经典题目
基础应用
- 最长公共子序列 - LeetCode 1143
- 两个字符串的删除操作 - LeetCode 583
LCS变体
多序列LCS
- 三个字符串的最长公共子序列
- K个字符串的最长公共子序列
⚖️ 优缺点
优点
- ✅ 经典DP问题：理解DP的好例子
- ✅ 应用广泛：版本控制、文本对比等
- ✅ 可扩展：可以求多个序列的LCS
缺点
- ❌ 时间复杂度O(mn)：大序列计算慢
- ❌ 空间复杂度高：虽然可以优化到O(n)
🎨 应用场景
- 版本控制：Git diff 的核心算法
- 文本对比：找出两个文档的公共部分
- 基因序列分析：比较DNA序列
- 数据同步：找出最少修改操作
- 拼写纠错：找相似单词
💡 LCS vs LCS（最长公共子串）
| 特性 | LCS（子序列） | 最长公共子串 |
|---|---|---|
| 连续性 | 不要求连续 | 必须连续 |
| 示例 | ”AC”是”ABC”和”ADC”的LCS | ”AB”是”ABC”和”DABC”的公共子串 |
| DP状态 | dp[i][j]表示长度 | dp[i][j]表示以i,j结尾的长度 |
| 复杂度 | O(mn) | O(mn) |
🔍 LCS的扩展
2. 最长回文子序列
最长回文子序列 = LCS(s, reverse(s))