CSCI3160 Special 7：LCS、共同子串与网格最长路径

原件：Sp07 题目（本地课件） p.1。每题先题解后解析；表格为原题数据的独立计算结果。

Problem 1：两条二进制串的完整LCS表

题解

x=10010101，y=010110110。完整opt表如下，最终长度为6。

i / j	1:0	2:1	3:0	4:1	5:1	6:0	7:1	8:1	9:0
0空	0	0	0	0	0	0	0	0	0
1:1	0	1	1	1	1	1	1	1	1
2:0	1	1	2	2	2	2	2	2	2
3:0	1	1	2	2	2	3	3	3	3
4:1	1	2	2	3	3	3	4	4	4
5:0	1	2	3	3	3	4	4	4	5
6:1	1	2	3	4	4	4	5	5	5
7:0	1	2	3	4	4	5	5	5	6
8:1	1	2	3	4	5	5	6	6	6

具体解析

首行、首列0；字符相等用左上加1，否则用上和左的较大者。比如opt(3,6)匹配0与0，等于opt(2,5)+1=3；opt(8,9)的1与0不匹配，取max(opt(7,9),opt(8,8))=6。按行填使每格的依赖已存在，一共9×10个状态（含空前缀边界）。

这个表不是编辑距离，也不是共同子串长度。某一格能继承左或上，是因为子序列允许删字符；连续子串不能这样继承。

Problem 2：恢复一个实际LCS

题解

一个LCS为100110，长度6。它在x中的位置可为1、2、3、4、6、7，在y中可为2、3、6、7、8、9。

具体解析

从(8,9)回溯，字符不同且平局时向上。路径为(8,9)→(7,9)→(6,8)→(5,7)→(4,7)→(3,6)→(2,5)→(2,4)→(2,3)→(1,2)→边界。

对角移动的格子依次收集0、1、1、0、0、1，这是从末尾往前恢复的顺序，反转得100110。上移或左移不输出字符。提供两串中的匹配下标验证它确实是公共子序列，再由Q1最大长度6保证它最长；只给一个可匹配的串而不说明长度最优，还缺半个证明。

Problem 3：最长共同子串

题解

定义D[i,j]为必须同时在x[i]、y[j]结尾的最长共同连续子串长度。字符相同则D[i,j]=D[i−1,j−1]+1，否则为0。答案取所有格子最大值，记录其x端点i即可输出x[i−D+1:i]。时间O(nm)。

具体解析

末字符不同，不存在以这两个位置结尾的非空相同串，所以必须清零，不能取上、左最大。末字符相同则共同连续后缀之前的所有字符仍必须对齐，所以只能由左上延长。

自取x=ABABC、y=BABCA：在x[5]=C、y[4]=C处得到4，对应BABC；它前面三个匹配格依次是(4,3)的B、(3,2)的A、(2,1)的B。最大值不一定出现在(n,m)，所以维护全局最大。表可滚动成O(m)辅助空间，仍记录最佳端点和长度恢复原串切片；若两个串没有共同字符，返回空串。

Problem 4：网格递增路径，排序后DP

题解

把n×n网格视为n²个顶点，若相邻且值从小到大，连一条有向边。按值降序处理格子，令L(u)=1+max{L(v):v为相邻更大格}，没有更大邻居时L(u)=1。保存最大邻居指针，从最大L格出发恢复路径。时间O(n²log n)。

具体解析

本题路径长度数格子数，所以基例为1。原题将逐步约束写成k∈[2,n]，应按路径中全部相邻步骤k=2,…,ℓ理解；否则长度大于n的后半路径没有约束，显然不符合题意。

值严格增加意味着有向环不可能出现：绕回原格要求原值严格小于自身。要算从u开始的最长路，就依赖更大的邻居，因此按降序填。每格最多检查四个邻居，DP本身O(n²)，排序n²项需O(n²log(n²))=O(n²log n)，空间O(n²)。

自取网格两行为[1,2]、[4,3]：按4、3、2、1处理，L分别1、2、3、4，恢复1→2→3→4。只允许上下左右，不能把对角格当邻居；排序只决定计算先后，不代表排序中相邻的两个格可直接相连。

Problem 5：去掉排序得到线性格子数时间

题解

使用记忆化DFS求同一个L(u)。首次访问u时递归求全部更大邻居，算出最大值后缓存；之后再访问直接返回缓存。每格只完整展开一次，每条邻接关系只检查常数次，总O(n²)。

具体解析

严格递增已经保证依赖无环，所以不需要排序来防止递归循环。按需DFS天然先完成依赖再计算当前状态。必须遍历所有格子并取最大起点，不能仅从最小值格出发：它未必能通向最长路线。

Solve(u)：
    若已有L[u]：返回L[u]
    L[u] ← 1
    对四邻居v：
        若M[v]>M[u]：
            候选 ← 1+Solve(v)
            若候选更大：更新L[u]与next[u]
    返回L[u]

记忆表和最坏递归栈都可能O(n²)。若运行环境栈较小，可统计每格“更大邻居数”，从没有更大邻居的格子入队，按逆依赖逐步消除，得到同样线性复杂度且避免深递归。空间上不能误称O(n)：格子总数是n²。

严格递增是记忆化能够终止的理由。 原题规定所有数互异；为了区分这个输入条件与严格移动规则，另看允许重复数的扩展实例：全 1 二乘二网格：没有允许的移动，每个状态直接返回 1，所以最长路径长度是 1 个格子。如果悄悄改成“非递减”，相邻两个 1 就可相互递归；此时“进入状态便先写 L=1”不能当作正确的已完成缓存，只会用未算完的值切断循环。原题严格递增使每条递归边都朝更大数值走，不可能回到调用栈上，所以无需为环另设语义。

自测：线性时间是否也意味着常数辅助空间？

不是。每格只求解一次给出 $O(n^2)$ 时间，但缓存本身有 $n^2$ 个状态，某些蛇形严格递增排列还会形成长达 $n^2$ 的递归链；调用栈也可能达到这个数量级。改迭代拓扑 DP 可避免语言栈限制，但仍需保存状态。

来源与证据

Sp07 p.1；完整LCS表与恢复序列已独立计算，并检查两串中的位置匹配。