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为什么这个方法成立
- 空前缀基础正确。
- 相等末尾可扩展较短前缀,存在使用这一共同末尾的最优解。
- 不相等时任一最优解至少不使用一边末尾,取两种可能最大值穷尽最优方案。
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从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
'abc' 与 'def' 的答案?
需要一点提示
无共同字符。
查看解析与答案
0。
'ab' 与 'ba' 的 LCS 唯一吗?
需要一点提示
a、b 都可。
查看解析与答案
长度 1,不唯一。
如何由 LCS 求仅插入删除的编辑次数?
需要一点提示
保留共同序列,其他分别删和加。
查看解析与答案
若长度为 L,则需要 (n−L)+(m−L)=n+m−2L 次;若允许替换,这个公式不再等价。