Vince Jiang

CSCI3160 / 课程伴读 · 本站更新

CSCI3160 L09 最长公共子序列与回溯

课程：CSCI3160 Design and Analysis of Algorithms 本讲：L09 最长公共子序列与回溯 · 原件 L09-DP-04-Longest-Common-Subsequence-未核-隐藏.pdf（本地课件） p.1–11 定位：从不交叉匹配证明 LCS 递推，再从长度表恢复一条实际公共子序列。 承接：#L08-03 二维递推；#L07-02 Piggyback

p.1 标题页。

可以删除，不能改顺序（p.2–3）【新】

p.2 A string s is a subsequence of another string t if either s = t or we can convert t to s by deleting characters.

p.2 的子序列（subsequence）允许跳过字符，但保留顺序。ABCDEF 的 ABD、ACDF、ABCDEF 自身都合法；ACB 把 B 放在 C 后，不合法；ACG 含原串没有的 G；BDFE 让 E 在 F 后，也不合法。它不同于 L08 连续的 substring。

题面（L09-DP-04-Longest-Common-Subsequence-未核-隐藏.pdf · LCS · p.3）

p.3 Given two strings x and y, find a common subsequence z of x and y with the maximum length. Example: If x = ABCBDAB and y = BDCABA, then BCBA is an LCS of x and y, so is BCAB. If x = ∅ (empty string) and y = BDCABA, their (only) LCS is ∅.

p.3 既要在两个串都出现，又要长度最大。BCBA 与 BCAB 都长 4，最优字符串可以不唯一；空串与任何串的 LCS 只能为空，这给出递推边界。

匹配图让顺序条件可见（p.4–5）

图（p.4）：BCBA 在两串中的对应匹配。 元素：上排 ABCBDAB，下排 BDCABA；红边依次连接上排位置 2、3、4、6 与下排位置 1、3、5、6。 看什么：两边下标均严格递增，因此边可从左到右排列；不允许复用一个字符位置，也不允许交叉匹配。

p.5 开始寻找递归结构。看末尾字符的意义是：匹配图最右的一条边决定了能否同时使用两个串的最后位置，从而把问题缩成更短前缀。

两个末字符的两种情况（p.6–7）

p.6 If x[n] = y[m], there exists an LCS z of x and y satisfying both of the following:

p.6 第一条只说存在一个最优匹配让两个末字符相配，不说每个 LCS 的每种匹配都如此。去掉这对字符后，余下必须是两个更短前缀的 LCS，否则可用更长的替代它，得到更长原解。

第二条说末字符不同，任何 LCS 至少不使用其中一个末位置，故可取“去 x 末尾”和“去 y 末尾”两种问题中较大的答案。

p.7 第一例 x=BCBDA、y=BDCABA，BCBA 可让末尾 A 对 A；第二例 x=ABCBDAB、y=BDCABA，BCBA 不使用 x 最后一个 B。关键是删除位置，不是删掉该字母在整个串中的所有出现。

为什么相同可以配，不同必须丢一边（p.8–9）

p.8 取一个 LCS 的最右匹配边。如果两端都不是最后位置，而末字符相同，就可额外追加这对末字符，与最长性矛盾；若只一端用到最后位置，则把该边另一端移到对应末位置，字符仍相同，先后顺序不破坏，长度不变。这就构造出想要的最优匹配。

p.9 末字符不同时不可能相配。也不能分别都匹配在对方更早的位置，否则两条边交叉，违背顺序。因此至少一个末位置未使用。若删该位置后还有更长公共子序列，它在原串中也合法，又与最长性矛盾。

补充：递推的两个方向都要证明。 以末字符不同为例，任何原问题的公共子序列至少没用一个末位置，所以长度不超过两个删尾子问题最优值的最大者，这是上界。反过来，删尾后的公共子序列也一定是原串的公共子序列，因此两个子问题较大的那个值可以实际做到，这是下界。上下界相等，才说明取 max 是完整递推，而不是只找到一个可行启发式。

若末字符相同，把两个短前缀的一条 LCS 接上这个字符，可以实际做到“左上加 1”；存在一个末尾配对的最优解又保证不会更长。这里“相同就配”是存在性结构性质，不是在穷举全部最优匹配。

自测：x=AB、y=BA 的最后两个字符不同，为什么不能直接都删除？

分别删一边得到 LCS 长度 1；若强制同时删除，则只比较 A 与 B，错误地得到 0。正确转移需要保留“只放弃一个末位置”的两种可能。原题最优解既可为 A 也可为 B；并列回溯只选其中一种是允许的。

再进一步：找到长度 1 的公共子序列，已经证明它最长了吗？

还没有。构造只说明最优值至少为 1；这里完整 DP 的上界，或说明两串次序相反不可能共同保留两个字符，才排除长度 2。

填完整张长度表（p.10）【延伸 L08 p.4–9】

p.10 opt(i,j) = the LCS length of x[1:i] and y[1:j].

本页约定 x[1:0]=y[1:0]=∅x[1:0]=y[1:0]=\varnothing；∣s∣\lvert s\rvert 表示字符串 s 的字符数。完整递推留在本篇，公式按讲义重排：

opt(i,j)={0i=0 or j=0,opt(i−1,j−1)+1i,j>0 and x[i]=y[j],max⁡{opt(i,j−1),opt(i−1,j)}i,j>0 and x[i]≠y[j]. \mathrm{opt}(i,j)=\begin{cases} 0 & i=0\text{ or }j=0,\\ \mathrm{opt}(i-1,j-1)+1 & i,j>0\text{ and }x[i]=y[j],\\ \max\{\mathrm{opt}(i,j-1),\mathrm{opt}(i-1,j)\} & i,j>0\text{ and }x[i]\ne y[j]. \end{cases}

i、j 分别是两个前缀的长度；opt 是最优长度，不是那个字符串本身。这给 #L08-03 的函数补上语义。相同末字符取左上加 1，不同取左与上最大，空前缀为 0。按讲义 p.3 原串计算如下：

x／y 空 B D C A B A
空 0 0 0 0 0 0 0
A 0 0 0 0 1 1 1
B 0 1 1 1 1 2 2
C 0 1 1 2 2 2 2
B 0 1 1 2 2 3 3
D 0 1 2 2 2 3 3
A 0 1 2 2 3 3 4
B 0 1 2 2 3 4 4

例：opt(4,5) 两个字符都是 B，左上 opt(3,4)=2，故得 3；opt(5,5) 是 D 对 B，取 max(2,3)=3；opt(6,6) 是 A 对 A，左上 3 加 1 得 4。最后一格 4 是全局最优长度，不只是找到某条长度 4 的序列。

回溯得到字符串（p.11）【延伸 L07 p.6–8】

p.11 This can be done by using the piggyback technique introduced in the previous lecture.

每格记录取值来自哪里：相同字符走左上并记录字符；不同时走达到最大值的上格或左格。并列时任选一条，不必枚举所有 LCS。

算一遍：从 (7,6) 取上格到 (6,6)，匹配 A，走 (5,5)；再向上到 (4,5)，匹配 B，走 (3,4)；向左到 (3,3)，匹配 C，走 (2,2)；向左到 (2,1)，匹配 B，走 (1,0) 停止。逆序记录为 A、B、C、B，反转得到 BCBA。核验位置正是 p.4 的 (2,3,4,6) 与 (1,3,5,6)。

把 p.11 的恢复细节写成可以照着执行的过程：

先把第 0 行、第 0 列置 0
按 i 从 1 到 n、j 从 1 到 m 填 opt 表
相同字符时记录 diagonal；否则记录达到最大值的 up 或 left
令 i=n，j=m，reversed=空序列
当 i>0 且 j>0：
  若方向是 diagonal：追加 x[i]；i 减 1；j 减 1
  若方向是 up：i 减 1
  若方向是 left：j 减 1
把 reversed 的字符次序反转后输出

回溯每步让 i 或 j 至少减 1，最多 n+m 步；填表仍主导总时间 O(nm)O(nm)。不能把“按表回溯”写成重新搜索全部匹配，否则会丢掉动态规划的效率。

考试角度：（C 级 通识）常见考法是给两串填长度表并回溯；必须说明并列选择可能得到另一条同样长的 LCS。

对应往年题见附录 A1。

本讲核心考点

  • 子序列允许跳字符但不许改变顺序（p.2–4，C 级）。
  • 末字符相同存在最优配对，不同至少丢弃一端（p.6–9，C 级）。
  • 长度表与选择回溯共同输出实际LCS（p.10–11，C 级）。

附录

本讲所需过程已在正文展开。

A1 作业/往年题演练（非讲义内容）：最长递减子序列

题面（Final-2021T1-题解.pdf · Part II Q4 · PDF p.4 左栏，印刷 p.7；扫描件，视觉读取）

p.4 “4. Determine the length of a longest decreasing subsequence (e.g., 31, 28, 27 is a decreasing subsequence) in the following sequence:”

“31, 33, 28, 27, 29, 25, 31, 27, 26, 30, 23, 17, 18, 21, 22, 28, 17, 15, 21.”

这里要严格递减，不能选两个相等的27。可把原序列与其不同数值的递减排序序列求LCS：后者为33、31、30、29、28、27、26、25、23、22、21、18、17、15。共同子序列必严格递减；反过来任何严格递减子序列必是这个排序序列的子序列，因此最大长度相等。

补充核算：也可用一维DP更紧凑地展示同一答案。令D(i)为必须以第i个数结尾的最长严格递减子序列长度，D(i)=1+max{D(j)：j<i且A[j]>A[i]}，候选为空时取1。沿原序列，各格为1、1、2、3、2、4、2、3、4、3、5、6、6、6、6、3、7、8、7。第18格的15可以接在第17格17后，其D值为7+1=8；第19格21不能接在更小的15或17后，只能接在例如第15格22后，所以是7。最大8，一条实现序列为33、28、27、25、23、18、17、15，原位置2、3、4、6、11、13、17、18严格递增，数值严格递减。按状态数乘枚举前驱数，两种演练实现都是二次方时间。

回到正文：本讲结尾

来源与证据

  • 本次逐页复核：2026-10-13，依据上述本地课件；保留已发布深化内容，页码指 PDF 物理页。历史考试演练保留其原有出处，本次不将旧记录冒充重新阅卷。

  • 原件：L09-DP-04-Longest-Common-Subsequence-未核-隐藏.pdf（本地课件）；页码均为 PDF 页号。

  • 版本记录（2026-09-17）：当时从教师官网下载并逐字节核对，与本地原件一致；此日期不是本次重新联网核验。原始学期未核，不据网页学期补猜。

  • 发布状态（2026-09-17 核验时）：官网链接所在行隐藏，当时按预习参考处理；不据此推断后续发布或考试范围。

  • 既有考试证据记录（2026-09-17）：当时读取了教师官网、Midterm-2021T1-题目.pdf、Midterm-2021T1-题解.pdf、Review-Quiz-2020T2-题目.pdf、Review-Quiz-2020T2-题解.pdf、Quiz-01-2025T1-题解.pdf、Midterm-A-2025T1-缺题干-解答.pdf、Quiz-02-2025T1-缺题干-解答.pdf、Quiz-03-2025T1-缺题干-解答.pdf、Final-2021T1-题解.pdf、Final-2024T1-缺判断-题目.pdf、Final-2025T1-题目.pdf、Final-2025T1-缺题干-解答.pdf；未识别用途的 PDF：无

  • 缺题干解答卷仅用于核对已取得的题面，不由答案反推题目。