最长公共子序列（LCS）——找到两个序列中共同的最长“影子”
较难2概述：从两个字符串（或数字序列）中，分别挑出一些字符，保持各自顺序相同，找到这样的最长子序列。
最长公共子序列（LCS）：找两个序列共同的最长“影子”——动态规划进阶
你有没有遇到过这样的情况：你和好朋友各自列了一张自己最爱看的动漫清单（按时间顺序），你们想找出哪些动漫是两人都看过，并且在各自清单里顺序还保持一致，这样的共同动漫最多可以有多少部？这就是最长公共子序列（Longest Common Subsequence，简称 LCS）要解决的问题。它就像一个“影子”，在两个序列中悄悄出现，保持原顺序，但不要求连续。
生活中的例子：找共同喜欢的歌
小红和小明都喜欢听歌，他们各自有一个歌单，按时间顺序记录了最近听的歌：
- 小红歌单：["青花瓷", "双截棍", "七里香", "菊花台"]
- 小明歌单：["双截棍", "菊花台", "夜曲", "青花瓷"]
他们想找出两人都听过，并且顺序不能乱的最长共同歌单。这里注意：可以跳过一些歌，比如小红有“青花瓷”和“七里香”，小明只有“青花瓷”没有“七里香”，那就只选“青花瓷”。最终共同歌单可能是["青花瓷","菊花台"]（长度2）或者["双截棍","菊花台"]（长度2），但最长能到多长呢？让我们用动态规划来算。
核心思路：二维表格记状态
想象画一张表格，行是第一个序列的每个位置，列是第二个序列的每个位置。每个格子 dp[i][j] 表示：第一个序列的前 i 个字符（或元素）和第二个序列的前 j 个字符（或元素）的最长公共子序列长度。
状态转移公式
- 如果当前两个字符相等（比如 a[i-1] == b[j-1]），那么它们可以成为公共子序列的一部分，长度等于去掉这两个字符后的结果加 1：
dp[i][j] = dp[i-1][j-1] + 1 - 如果不相等，那说明当前这两个字符不能同时加进公共序列，我们需要看“去掉一个”的情况：要么不包含 a[i-1]，要么不包含 b[j-1]，取这两种情况的最大值：
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
初始状态
空序列和任何序列的公共子序列长度都是 0，所以 dp[0][j] = 0，dp[i][0] = 0。
一步一步填表：用手画出来更容易懂
我们用一个简单的例子：a = "abcde", b = "ace"。表格如下（行列从0开始）：
"" a c e
"" 0 0 0 0
a 0 1 1 1
b 0 1 1 1
c 0 1 2 2
d 0 1 2 2
e 0 1 2 3
- 第1行第1列：a vs a → 相等，dp[1][1]=dp[0][0]+1=1
- 第1行第2列：a vs c → 不等，取左和上最大值，左=dp[1][1]=1，上=dp[0][2]=0，所以1
- 一直填到右下角3，就是答案。
注意：为什么是3？因为公共子序列是"ace"。
Python代码实现：求长度
下面的函数计算两个字符串的最长公共子序列长度。
def longest_common_subsequence_len(a, b):
m, n = len(a), len(b) # m为a的长度，n为b的长度
# 创建一个 (m+1) x (n+1) 的二维列表，初始全0
dp = [[0] * (n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if a[i-1] == b[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]
# 测试
print(longest_common_subsequence_len("abcde", "ace")) # 输出3
print(longest_common_subsequence_len("tgb", "tgb")) # 输出3（完全相同）
print(longest_common_subsequence_len("abc", "def")) # 输出0（无共同字符）
不只求长度：如何找回LCS本身？
有时候我们不光想知道长度，还想知道具体是哪几个字符。这时需要回溯：从右下角出发，如果当前位置字符相等，就记下这个字符，然后向左上角走；如果不相等，就根据 dp[i-1][j] 和 dp[i][j-1] 谁大决定往上还是往左。下面的代码同时返回长度和子序列。
def longest_common_subsequence(a, b):
m, n = len(a), len(b)
# 创建dp表
dp = [[0] * (n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
# 回溯找出LCS字符串
i, j = m, n
lcs_chars = [] # 存储LCS的字符列表（倒序）
while i > 0 and j > 0:
if a[i-1] == b[j-1]:
lcs_chars.append(a[i-1]) # 相等时，加入结果
i -= 1
j -= 1
elif dp[i-1][j] >= dp[i][j-1]: # 往上走
i -= 1
else: # 往左走
j -= 1
lcs_str = ''.join(reversed(lcs_chars)) # 反转得到正序
return dp[m][n], lcs_str
# 测试
length, lcs = longest_common_subsequence("abcde", "ace")
print(f"长度: {length}, LCS: {lcs}") # 长度: 3, LCS: ace
length2, lcs2 = longest_common_subsequence("青花瓷双截棍七里香菊花台", "双截棍菊花台夜曲青花瓷")
print(f"长度: {length2}, LCS: {lcs2}") # 输出：长度: 2, LCS: 双截棍菊花台（或青花瓷菊花台，取决于回溯方向）
生活中的其他例子：排队、做作业顺序
- 排队顺序：班级要排一个长队做操，但有两个老师各自排了不同的队伍（保留原有顺序），想找出一个子序列，让两个老师都满意（即两个队伍中都按这个顺序出现）。比如老师A排：小明、小红、小刚、小丽；老师B排：小红、小丽、小明。LCS可能是小明、小丽（或小红、小丽），长度2。
- 做作业顺序：你有两个作业清单：数学、语文、英语、科学；和另一个同学的清单：语文、数学、科学。你们想一起写作业，但必须保持各自原来的顺序（比如不能先写数学再写语文，而顺序要一致）。LCS是“语文、科学”或“数学、科学”，长度2。
新手容易犯的错误
- 索引混淆：循环中
i从1到m，比较时用a[i-1]而不是a[i]，因为dp表的第一行/列对应空字符串。新手容易忘记减1，导致越界或错误。 - 初始化跳过：忘记
dp[0][j]和dp[i][0]都是0，但Python中创建列表时已初始化为0，没问题。但如果手动初始化，注意不要漏掉。 - 回溯时条件判断：回溯时
if a[i-1] == b[j-1]要写在前面，否则会被改变方向。另外注意>=和>的选择：当左边和上边相等时，取哪个方向都可以，但会影响最终LCS结果（可能有多个解）。 - 用
append后忘记reverse：回溯时从后往前添加，最终要反转字符串。
完整可运行代码示例
把所有功能整合在一个文件里，包含输入输出。
def lcs_length_and_string(a, b):
"""返回(a,b)的最长公共子序列长度和字符串"""
m, n = len(a), len(b)
# dp表：dp[i][j] 表示 a的前i个和b的前j个的LCS长度
dp = [[0] * (n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
# 回溯
i, j = m, n
chars = []
while i > 0 and j > 0:
if a[i-1] == b[j-1]:
chars.append(a[i-1])
i -= 1
j -= 1
elif dp[i-1][j] > dp[i][j-1]:
i -= 1
else:
j -= 1
lcs_str = ''.join(reversed(chars))
return dp[m][n], lcs_str
# 测试不同例子
examples = [
("abcde", "ace"),
("abcd", "abcd"),
("abcd", "dcba"),
("TGAC", "TGA"), # 基因序列类比
("我爱编程", "编程爱我")
]
for a, b in examples:
length, lcs = lcs_length_and_string(a, b)
print(f"序列1: {a}, 序列2: {b}")
print(f"LCS长度: {length}, LCS: '{lcs}'")
print("-" * 30)
输出结果：
序列1: abcde, 序列2: ace
LCS长度: 3, LCS: 'ace'
------------------------------
序列1: abcd, 序列2: abcd
LCS长度: 4, LCS: 'abcd'
------------------------------
序列1: abcd, 序列2: dcba
LCS长度: 1, LCS: 'a' (或b/c/d，取决于回溯)
------------------------------
序列1: TGAC, 序列2: TGA
LCS长度: 3, LCS: 'TGA'
------------------------------
序列1: 我爱编程, 序列2: 编程爱我
LCS长度: 2, LCS: '我爱' (或'编程'？实际上'我爱'是公共的且顺序一致)
------------------------------
相关知识点指引
- 最长公共子串：要求连续，用动态规划时公式不同（相等时
dp[i][j] = dp[i-1][j-1] + 1，不相等时dp[i][j] = 0）。LCS是不连续版。 - 编辑距离（Levenshtein距离）：将字符串A变成B需要的最少编辑操作（插入、删除、替换），动态规划思想和LCS类似，但转移公式更丰富。
- 贪心与DP：LCS不能用贪心，只能用动态规划，因为局部最优不一定全局最优。比如"abc"和"acb"，贪心匹配a后，会选c，但后面b无法匹配；而最优是"ab"或"ac"。
- 空间优化：LCS的二维表可以优化成一维滚动数组，因为每次只用上一行和当前行左边，但回溯时仍需完整表。
掌握了LCS，你就打开了二维动态规划的大门。下一个可以挑战“最长公共子串”或“最大子序列和”，它们都是DP里的经典题目。
例题精讲
1单选题
下列关于最长公共子序列（LCS）的描述，哪一项是正确的？
ALCS一定是原字符串中的连续子串
BLCS的长度可能大于两个原字符串中较短者的长度
CLCS可能存在多个不同的序列，但它们的长度相同
DLCS问题可以通过贪心算法在多项式时间内得到最优解
2判断题
在计算最长公共子序列长度的动态规划中，初始化dp[0][j]=0（j从0到n）和dp[i][0]=0（i从0到m）是正确的。
3判断题
在回溯构造最长公共子序列时，如果当前字符X[i-1]==Y[j-1]，则将该字符加入结果，并继续回溯(i-1, j-1)；否则，如果dp[i-1][j] > dp[i][j-1]，则向上移动；如果dp[i-1][j] == dp[i][j-1]，可以任意选择一个方向，仍能得到一个最长公共子序列。
4填空题
以下函数用于计算两个字符串的最长公共子序列长度。请填写else分支中的代码。
def lcs_length(s1, s2):
m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = ___5填空题
以下是用一维滚动数组优化空间复杂度的LCS长度计算函数。请填写两个填空位置。
def lcs_length_optimized(s1, s2):
m, n = len(s1), len(s2)
dp = [0] * (n+1)
for i in range(1, m+1):
prev = 0
for j in range(1, n+1):
temp = dp[j]
if s1[i-1] == s2[j-1]:
dp[j] = ___(1)___
else:
dp[j] = ___(2)___
prev = temp
return dp[n]