专题进阶 · 动态规划推荐总顺序 · 第 70 / 148 课

用两个前缀定义状态,从末尾字符是否相同推导最长公共子序列。

先学会这些,再进入本课 二维 DP 字符串
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 动态规划

最长公共子序列LCS

比较两个前缀的末尾字符,相同则接续,不同则舍弃一侧末尾。

建议 40 分钟 · 含手算、代码与三层练习

本课要建立的能力

用两个前缀定义状态,从末尾字符是否相同推导最长公共子序列。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

字符串 'abc' 与 'ac',允许删除字符但不改变顺序,最长共同序列是什么?

02一步步得到方法

状态保留两边已考虑的范围

dp[i][j] 表示 a 的前 i 个字符与 b 的前 j 个字符的 LCS 长度。任一前缀为空时答案为 0,因此表多一行一列,避免不断判断负下标。

末尾相等时可将该字符接在两边更短前缀的共同序列后,得到 dp[i−1][j−1]+1;末尾不同,不可能同时用作同一个最后匹配,至少舍弃一边末尾,取上方与左方最大值。

公共子序列与公共子串区别

子序列可以跳过 a 中的 b,所以 abc 与 ac 的答案是 ac,长度 2。公共子串要求连续,本例最长只能为一个字符;它的状态和失配处理不同。

代码求长度。若需要字符串,可从右下回溯:相等取字符并同时回退,不等沿较大来源走;平局可能对应多条不同最优序列。

匹配与不匹配分别解释

比较两个前缀的最后字符。若相同,可以在较短两前缀的公共子序列后接上这个字符;若不同,最优解至少放弃一边的最后字符,取两个相邻子问题较大者。

回溯表格可恢复一条 LCS,平局可能产生多条不同最优答案。仅保存两行可求长度,但会丢掉直接回溯所需的整张决策信息,需要额外方法恢复。

03把一个小例子完全算清楚

a='abc',b='ac',列为 空、a、ac。

步骤计算与状态为什么这样做
空行[0,0,0]没有字符
a 行[0,1,1]a 匹配后长度 1
ab 行[0,1,1]b 不匹配,只能继承
abc 行[0,1,2]c 匹配,接到 a 后

窄屏可左右滑动表格,阅读完整计算与理由。

答案长度 2;二维表每个位置都对应两个明确前缀。

04为什么这个方法成立

  1. 空前缀基础正确。
  2. 相等末尾可扩展较短前缀,存在使用这一共同末尾的最优解。
  3. 不相等时任一最优解至少不使用一边末尾,取两种可能最大值穷尽最优方案。

05把推导翻译成代码

Python · 可独立运行的教学实现

def lcs_length(a,b):
    dp = [[0]*(len(b)+1) for _ in range(len(a)+1)]
    for i in range(1,len(a)+1):
        for j in range(1,len(b)+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[-1][-1]

逐个理解关键决定

a[i-1] == b[j-1]
表坐标是前缀长度,字符串坐标要减 1。
max(dp[i-1][j],dp[i][j-1])
失配时允许跳过一边,不是把计数归零。

06时间、空间与实现范围

时间 O(nm),本完整表空间 O(nm)。只求长度可滚动为 O(min(n,m)) 空间。

恢复序列需要保留决策或使用更复杂的线性空间分治,不能只靠最后两个标量。

07改变条件,检查哪里会出错

失配就置零

那更接近连续公共子串递推,会丢掉允许跳跃的序列。

把最长公共子串与子序列混用

子串要求连续,失配通常清零;子序列允许跳过,使用相邻状态最大值。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

'abc' 与 'def' 的答案?

需要一点提示

无共同字符。

查看解析与答案

0。

练习 2 · 边界与辨析

'ab' 与 'ba' 的 LCS 唯一吗?

需要一点提示

a、b 都可。

查看解析与答案

长度 1,不唯一。

练习 3 · 变式与迁移

如何由 LCS 求仅插入删除的编辑次数?

需要一点提示

保留共同序列,其他分别删和加。

查看解析与答案

若长度为 L,则需要 (n−L)+(m−L)=n+m−2L 次;若允许替换,这个公式不再等价。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

MIT 6.006 · 算法讲义

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。