动态规划解最长公共子序列：从暴力搜索到空间优化

1. 项目概述从“找茬”游戏到算法核心如果你玩过“找茬”游戏或者对比过两段代码、两篇文章的相似度那你其实已经在直觉上接触过“最长公共子序列”这个概念了。它要解决的就是如何在两个序列比如字符串、数组中找到那个最长的、且顺序一致的公共部分。这个“公共部分”不需要连续只要保持原有的先后顺序就行。听起来是不是有点像在两条时间线上寻找共同经历的关键事件在生物信息学里它被用来比对DNA或蛋白质序列寻找进化上的关联在版本控制系统中Git用它来比较两个文件版本的差异生成那行经典的diff输出在文本查重、语音识别甚至手机键盘的单词预测里你都能找到它的身影。而“动态规划”正是解决这类问题的一把瑞士军刀。它不是什么高深莫测的黑魔法其核心思想非常“人性化”面对一个复杂的大问题我们把它拆解成一系列小问题解决每个小问题时我们记下答案这就是“规划”当遇到重叠的小问题时直接查表用之前的答案避免重复计算这就是“动态”地利用历史。很多人初学动态规划会觉得它抽象但LCS问题堪称是展示动态规划思想最经典、最直观的“样板间”。今天我们就抛开那些枯燥的教科书定义像解一道有趣的智力题一样把LCS的动态规划解法掰开揉碎从为什么需要它到每一步怎么想再到代码怎么写、怎么优化最后聊聊实际编码时那些教科书上不会写的“坑”。无论你是正在备战面试的求职者还是对算法好奇的开发者相信这篇都能让你对LCS和动态规划有“原来如此”的透彻理解。2. 核心思路拆解为什么暴力搜索不行而动态规划可以在撸起袖子写代码之前我们得先想明白为什么这道题非得用动态规划不用行不行我们来推演一下。2.1 暴力枚举的灾难指数级复杂度假设我们有两个字符串A “ABCBDAB”B “BDCABA”。最直接的想法是暴力枚举找出字符串A的所有子序列再找出字符串B的所有子序列然后逐个比较找出最长的公共那个。一个长度为n的字符串它的子序列有多少个每个字符都有“选”或“不选”两种可能所以总共有2^n个子序列包括空序列。对于A长度7有128个对于B长度6有64个。我们需要比较128 * 64 8192次。这看起来对于现代计算机似乎还能接受但这是错觉。一旦字符串长度变成20A就有约100万个子序列B也有100万比较次数就是1万亿次。长度到30时这个数字将膨胀到10^18次即使每秒能进行10亿次运算也需要超过30年。这显然是不可行的。暴力法的复杂度是 O(2^m * 2^n)是指数级的是算法设计中需要极力避免的“灾难”。2.2 动态规划的切入点最优子结构与重叠子问题动态规划能解决问题必须满足两个关键性质而LCS完美符合最优子结构一个问题的最优解包含了其子问题的最优解。对于LCS假设我们已经知道A[1..i]和B[1..j]的LCS长度那么当我们要计算A[1..i1]和B[1..j1]时这个更大问题的解完全可以由前面那些更小问题的解推导出来。重叠子问题在递归地求解各个子问题时会反复遇到相同的、更小的子问题。如果我们傻傻地重复计算效率就和暴力法没区别了。动态规划的精髓就在于“记忆化”——把这些子问题的解存起来下次直接用。LCS的动态规划思路就源于一个非常简单的分类讨论。比较A[i]和B[j]时只有两种情况情况一A[i] B[j]。那么这个字符一定是公共子序列的一部分此时的LCS长度就等于A[1..i-1]和B[1..j-1]的LCS长度再加1。情况二A[i] ! B[j]。那么A[i]和B[j]不可能同时成为当前公共子序列的最后一个字符。此时的LCS长度只能来源于两种子问题中的最大值忽略A[i]看A[1..i-1]和B[1..j]的LCS。忽略B[j]看A[1..i]和B[1..j-1]的LCS。这个关系就是动态规划的状态转移方程。我们用一个二维数组dp来充当“备忘录”dp[i][j]就表示A的前i个字符和B的前j个字符的LCS长度。注意这里有一个初学者极易混淆的点。dp[i][j]表示的是“前缀”的LCS长度即A[0..i-1]和B[0..j-1]如果我们从0开始索引字符。在代码实现时我们通常会创建(m1) x (n1)的数组其中dp[0][j]和dp[i][0]都初始化为0表示一个字符串前缀和空字符串的LCS长度为0。这是为了给状态转移一个统一的起点。2.3 从递归到递推两种实现路径理解了这个核心关系后我们有两种实现方式自顶向下的记忆化搜索写一个递归函数lcs(i, j)在函数里先查表dp[i][j]是否计算过没计算过就按照上述两种情况递归调用lcs(i-1, j-1)、lcs(i-1, j)、lcs(i, j-1)并把结果存入dp[i][j]。这种方式更贴近我们对问题的自然思考。自底向上的递推直接用双层循环从小到大依次计算dp[i][j]。因为计算dp[i][j]时它所依赖的dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]都已经被计算出来了。这是更常见、更标准的动态规划写法空间和时间效率通常更直观。我们接下来会详细讲解自底向上的递推法因为它更基础也更容易转化为空间优化的版本。3. 算法详解与手动模拟理论说得再多不如手动算一遍来得实在。我们以A “ABCBDAB”B “BDCABA”为例来完整推演一遍动态规划表dp的填充过程。3.1 状态定义与初始化我们定义dp[i][j]为字符串A的前i个字符即A[0..i-1]与字符串B的前j个字符即B[0..j-1]的最长公共子序列的长度。 创建一张表格行对应A的每个字符0到m列对应B的每个字符0到n。dp[0][j]和dp[i][0]表示与空字符串的LCS显然都是0。初始表格如下第一行和第一列已填0B D C A B A 0 1 2 3 4 5 6 (j) --------------------- 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | --------------------- A 1 | 0 | | | | | | | --------------------- B 2 | 0 | | | | | | | --------------------- C 3 | 0 | | | | | | | --------------------- B 4 | 0 | | | | | | | --------------------- D 5 | 0 | | | | | | | --------------------- A 6 | 0 | | | | | | | --------------------- B 7 | 0 | | | | | | | --------------------- (i)3.2 状态转移方程与填表过程状态转移方程就是我们之前讨论的逻辑如果A[i-1] B[j-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])现在我们开始按行i从1到7按列j从1到6填表i1, j1: A[0]‘A’, B[0]‘B’不等。dp[1][1] max(dp[0][1], dp[1][0]) max(0, 0) 0i1, j2: A[0]‘A’, B[1]‘D’不等。dp[1][2] max(dp[0][2], dp[1][1]) max(0, 0) 0i1, j3: A[0]‘A’, B[2]‘C’不等。dp[1][3] max(dp[0][3], dp[1][2]) max(0, 0) 0i1, j4: A[0]‘A’, B[3]‘A’相等dp[1][4] dp[0][3] 1 0 1 1。这意味着“A”和“BDCA”的LCS是“A”长度为1。i1, j5: A[0]‘A’, B[4]‘B’不等。dp[1][5] max(dp[0][5], dp[1][4]) max(0, 1) 1i1, j6: A[0]‘A’, B[5]‘A’相等dp[1][6] dp[0][5] 1 0 1 1第一行填完。以此类推我们逐步填充整个表格。为了节省篇幅我直接给出最终填完的表格并解释几个关键单元格B D C A B A 0 1 2 3 4 5 6 --------------------- 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | --------------------- A 1 | 0 | 0 | 0 | 0 |[1]| 1 |[1]| --------------------- B 2 | 0 |[1]| 1 | 1 | 1 |[2]| 2 | --------------------- C 3 | 0 | 1 | 1 |[2]| 2 | 2 | 2 | --------------------- B 4 | 0 | 1 | 1 | 2 | 2 |[3]| 3 | --------------------- D 5 | 0 | 1 |[2]| 2 | 2 | 3 | 3 | --------------------- A 6 | 0 | 1 | 2 | 2 |[3]| 3 |[4]| --------------------- B 7 | 0 | 1 | 2 | 2 | 3 |[4]| 4 | ---------------------看几个例子dp[2][1](i2,j1): A[1]‘B’, B[0]‘B’相等。dp[2][1] dp[1][0] 1 011。dp[3][3](i3,j3): A[2]‘C’, B[2]‘C’相等。dp[3][3] dp[2][2] 1 112。这对应子序列“BC”。dp[5][2](i5,j2): A[4]‘D’, B[1]‘D’相等。dp[5][2] dp[4][1] 1 112。dp[7][6](i7,j6): 表格右下角的值4就是我们最终要求解的A和B整个字符串的LCS长度。3.3 重构LCS反向追踪dp表只告诉了我们长度是4那具体的LCS是什么我们需要从dp[m][n]开始反向追踪回去。追踪规则逆序进行从dp[7][6]开始如果A[i-1] B[j-1]那么这个字符属于LCS。将其记录然后移动到dp[i-1][j-1]。如果A[i-1] ! B[j-1]则比较dp[i-1][j]和dp[i][j-1]如果dp[i-1][j] dp[i][j-1]说明当前LCS更可能来自忽略A[i-1]的情况移动到dp[i-1][j]。否则移动到dp[i][j-1]。追踪路径用^表示向上表示向左\表示向左上dp[7][6]4, A[6]‘B’, B[5]‘A’不等。看dp[6][6]4和dp[7][5]4相等。这里出现了分支意味着LCS可能不唯一。我们约定优先向上走你也可以优先向左。移动到dp[6][6]。dp[6][6]4, A[5]‘A’, B[5]‘A’相等记录‘A’。移动到dp[5][5]。dp[5][5]3, A[4]‘D’, B[4]‘B’不等。dp[4][5]3,dp[5][4]2向上移动到dp[4][5]。dp[4][5]3, A[3]‘B’, B[4]‘B’相等记录‘B’。移动到dp[3][4]。dp[3][4]2, A[2]‘C’, B[3]‘A’不等。dp[2][4]1,dp[3][3]2向左移动到dp[3][3]。dp[3][3]2, A[2]‘C’, B[2]‘C’相等记录‘C’。移动到dp[2][2]。dp[2][2]1, A[1]‘B’, B[1]‘D’不等。dp[1][2]0,dp[2][1]1向左移动到dp[2][1]。dp[2][1]1, A[1]‘B’, B[0]‘B’相等记录‘B’。移动到dp[1][0]。到达边界结束。我们记录的顺序是逆序的’A’, ‘B’, ‘C’, ‘B’。反转后得到 “BCBA”。这就是一个LCS。如果我们当初在第一步选择向左走 (dp[7][5])可能会得到另一个LCS比如 “BDAB”。两者长度都是4。实操心得手动模拟填1到2个小表格是理解动态规划不可替代的一步。它能帮你直观地看到状态是如何依赖和传递的远比死记硬背代码有效。在面试白板 coding 时先画出dp表的框架和初始化然后向面试官解释填表过程最后写代码思路会非常清晰。4. 代码实现与空间优化理解了原理和过程代码实现就是水到渠成。我们先给出最标准的二维DP解法然后讨论如何优化空间。4.1 标准二维DP实现Python示例def longest_common_subsequence(text1: str, text2: str) - int: m, n len(text1), len(text2) # 创建 (m1) x (n1) 的dp表并初始化为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 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]) # 右下角的值即为LCS长度 return dp[m][n] # 重构LCS的函数 def build_lcs(text1: str, text2: str, dp: list) - str: i, j len(text1), len(text2) lcs_chars [] while i 0 and j 0: if text1[i - 1] text2[j - 1]: lcs_chars.append(text1[i - 1]) i - 1 j - 1 elif dp[i - 1][j] dp[i][j - 1]: i - 1 else: j - 1 return .join(reversed(lcs_chars)) # 测试 A “ABCBDAB” B “BDCABA” length longest_common_subsequence(A, B) print(f“LCS 长度: {length}”) # 输出: LCS 长度: 4 # 为了重构需要先得到dp表 dp [[0] * (len(B) 1) for _ in range(len(A) 1)] # ... (这里省略填表代码与上面函数内逻辑相同) lcs_str build_lcs(A, B, dp) print(f“一个LCS是: {lcs_str}”) # 输出可能是: 一个LCS是: BCBA时间复杂度O(m * n)因为要填充一个 m x n 的表格。空间复杂度O(m * n)用于存储dp表。4.2 空间优化滚动数组仔细观察状态转移方程你会发现在计算dp[i][j]时它只依赖于当前行的dp[i][j-1]、上一行的dp[i-1][j]和dp[i-1][j-1]。也就是说我们并不需要保存整个 m x n 的表格只需要保存两行上一行和当前行就足够了。我们可以将空间复杂度优化到 O(min(m, n))。def longest_common_subsequence_opt(text1: str, text2: str) - int: # 让text2是较短的那个以节省空间 if len(text1) len(text2): text1, text2 text2, text1 m, n len(text1), len(text2) # 只维护两行prev 代表上一行 (i-1)curr 代表当前行 (i) prev [0] * (n 1) curr [0] * (n 1) for i in range(1, m 1): for j in range(1, n 1): if text1[i - 1] text2[j - 1]: curr[j] prev[j - 1] 1 else: curr[j] max(prev[j], curr[j - 1]) # 当前行计算完毕准备下一轮迭代 prev, curr curr, prev # 交换引用现在prev是旧的curr即当前行curr被重置或复用 # 注意需要清空或重新初始化curr吗由于下一轮会覆盖所有j1的值只需确保curr[0]0。 # 而交换后新的curr是旧的prev其值除了curr[0]是0其他位置是上一轮的上上行数据但会被覆盖所以没问题。 # 更稳妥的做法是在交换后显式地将新的curr即旧的prev的第一个元素置0并保留其他位置因为会被覆盖。 # 但Python中我们直接让 curr [0] * (n1) 更清晰不过会创建新数组。这里采用交换并利用覆盖的特性。 # 循环结束后prev 存储的是最后一行的结果因为最后进行了一次交换 return prev[n]注意事项空间优化后我们失去了完整的dp表因此无法直接进行LCS序列的重构。如果题目要求输出具体的LCS就必须使用标准的二维DP表。这是一个典型的“时间-空间”权衡。在面试中可以先写出标准解法然后主动提出“如果只需要长度我们可以将空间优化到O(n)”这能很好地展示你的知识深度。5. 常见问题、变体与实战技巧动态规划题目懂了LCS就掌握了一大类问题的思考范式。下面是一些延伸和实战中容易遇到的问题。5.1 LCS相关问题变体最长公共子串要求子序列是连续的。状态定义需要微调dp[i][j]表示以A[i-1]和B[j-1]为结尾的公共子串的长度。转移方程变为如果字符相等dp[i][j] dp[i-1][j-1] 1否则dp[i][j] 0。最终答案是整个dp表中的最大值。最短公共超序列给出两个序列求一个最短的序列使得这两个序列都是它的子序列。SCS长度 len(A) len(B) - LCS长度。重构SCS时可以在回溯LCS的同时将非公共字符也按序插入。编辑距离一个非常经典的DP问题操作包括插入、删除、替换。其状态转移方程与LCS有神似之处dp[i][j]表示将A的前i个字符转换为B的前j个字符所需的最少操作数。多个序列的LCS对于三个或更多序列思路类似但状态维度会增加三维、四维dp数组复杂度呈指数增长通常需要针对具体场景优化或使用近似算法。5.2 实战编码与调试技巧下标处理这是最容易出错的地方。坚持使用“dp[i][j]对应A[0..i-1]和B[0..j-1]”这个定义并在访问字符串时统一使用A[i-1]和B[j-1]。在初始化dp[0][j]和dp[i][0]为0后循环从i1, j1开始。数组初始化在Python中用[[0]*(n1) for _ in range(m1)]来创建二维数组。切忌使用[[0]*(n1)]*(m1)这样会导致内部的子列表是同一个对象的引用修改一个会影响到其他行。打印dp表调试当结果不对时别干瞪眼。将dp表完整打印出来和你手动模拟的表格对比能快速定位逻辑错误。对于小规模测试用例这是最有效的调试方法。处理空输入总是考虑边界情况。如果其中一个字符串为空LCS长度显然为0。你的代码应该能正确处理m0或n0的情况。通常我们的dp表定义已经包含了这种情况dp[0][j]0。重构路径不唯一如前所述当dp[i-1][j] dp[i][j-1]且字符不等时回溯路径会有分支代表存在多个LCS。你的重构函数可能只返回其中一条。在面试中如果被问到要能指出这一点并说明如果需要所有LCS需要用回溯法进行搜索。5.3 性能考量与进阶复杂度O(mn) 的时间和 O(mn)或O(n)的空间对于大多数字符串比较场景如文本diff、DNA中等长度序列比对是完全可以接受的。例如比较两个几千字的文档百万级别的操作在现代计算机上瞬间完成。超大字符串处理如果序列长度极大如数十万O(mn)的复杂度可能成为瓶颈。此时需要考虑更高级的算法如 Hunt–Szymanski 算法基于匹配点或使用位并行技术进行优化但这些通常只在特定领域如生物信息学的底层库中实现。与其它算法的关系LCS的DP解法和“最长递增子序列”LIS问题有内在联系。实际上如果将一个序列转化为另一个序列的“位置映射”LCS问题可以在某些条件下转化为LIS问题从而利用O(n log n)的LIS算法来求解达到更高的效率。这是一个很好的进阶思考方向。我个人在最初学习动态规划时LCS这个问题让我真正开了窍。它像一根线把“状态定义”、“状态转移方程”、“填表顺序”、“空间优化”这几个散落的珠子串了起来。后来遇到复杂的DP问题我总会先想能不能像LCS那样定义出一个有明确意义的dp[i][j]它的值怎么从之前的状态过来想明白了这些问题就解决了一大半。最后分享一个小心得在面试中遇到DP问题如果一下子想不出最优解可以先从暴力递归开始写然后画出递归树指出哪里存在“重叠子问题”再自然引出需要“记忆化”自顶向下最后优化成“递推”自底向上并讨论空间优化。这个思考过程比直接背出标准答案更能体现你的算法功底。