CSCI3160 Regular 7：LCS、矩阵链与序列 DP

原件：题目（本地课件）；官方答案（本地课件） p.1–4。定位：定义状态时保留足够的端点条件，并在填值时记录恢复方案的信息。

题意为概述，所有自取演算均单独标明。数组采用 1 起始下标。

Problem 1：末字符相同对所有 LCS 有何约束（答案 p.1）

设非空串 x、y 的最后字符同为 c，z 是任意最长公共子序列，长度 k。若 z 的末字符不是 c，则它在两个原串中的匹配位置都必然在末尾之前，可以同时把两个末尾 c 接上，得到更长公共子序列，矛盾。所以 z 的末字符必须为 c。

删去 z 最后一个字符后，剩下 k−1 个字符可匹配在两串各自删去末字符的前缀中：它们的位置都在 z 最后字符的匹配位置之前，自然也在原串最后位置之前。若这个前缀子序列不是前缀对的 LCS，则存在长度至少 k 的更长公共子序列，后面再接 c 就得到至少 k+1，矛盾。

注意“z 末字符是 c”不代表某个既定匹配方式必须使用两串最后位置；重复字符可能给出不同位置匹配，但可以把最后匹配换到末尾。官方第二段把“比 z 的前 k−1 字符长”简写成“比 z 长”，严格比较应按以上长度关系处理。

自取 x=BAC、y=ABC：LCS 可为 AC 或 BC，都以 C 结尾；删末尾后，A、B 都是 BA 与 AB 的 LCS。结论不要求 LCS 唯一。

Problem 2：从 DP 表恢复一个 LCS（答案 p.1–2）

先填长度表 D。D[0,j]=D[i,0]=0；字符相同取 D[i−1,j−1]+1，否则取 max(D[i−1,j],D[i,j−1])。按行或列求值花 O(nm)。恢复从 (n,m) 开始：

ans ← 空列表；i ← n；j ← m
当 i>0 且 j>0：
    若 x[i]=y[j]：把 x[i] 追加到 ans；i--；j--
    否则若 D[i-1,j] ≥ D[i,j-1]：i--
    否则：j--
反转 ans 并输出

相同时选这个字符，并进入能实现剩余最优长度的左上状态；不同时至少有一个最优解不使用其中一个末字符，沿较大的相邻值走。平局可任选，得到某一个最优解。

自取 x=ABC、y=BAC，从 (3,3) 先收 C；(2,2) 的 B 与 A 不同且上左平局，向上到 (1,2)，收 A，逆序列表为 C,A，反转得到 AC。回溯每次使 i+j 至少减一，时间 O(n+m)，总时间 O(nm+n+m)。对非空输入通常写 O(nm)。不要每次在不可变字符串头部拼接导致重复复制；列表收集后反转即可。

Problem 3：矩阵链乘法的最后一次乘法决定切点（答案 p.2）

设矩阵 i 的尺寸为 $p_{i-1}\times p_i$ 。状态 D[i,j] 是计算第 i 到 j 个矩阵乘积所需的最少标量乘法次数；单个矩阵 D[i,i]=0。

如果最后一次乘法在 k 处分割，左右结果尺寸分别为 $p_{i-1}\times p_k$ 和 $p_k\times p_j$ ，合并花 $p_{i-1}p_kp_j$ 次。因此

D[i,j]=\min_{i\le k<j}\{D[i,k]+D[k+1,j]+p_{i-1}p_kp_j\}.

按链长 2,…,n 填表，同时保存 split[i,j]。每个状态枚举 O(n) 个切点，O(n²) 状态，时间 O(n³)、空间 O(n²)。恢复时输出左区间括号、右区间括号并组合；二叉分解树 O(n) 个节点，所以恢复本身 O(n)，不必像官方宽松上界那样再花三次方时间。

自取尺寸 10×30、30×5、5×60：先乘前两者花 1500，再乘第三个花 3000，总 4500；先乘后两者花 9000，再与第一个乘花 18000，总 27000。两种方案输出矩阵尺寸相同，但中间矩阵大小很不同。

严谨口径。 不能把大 O 表达式本身当作可比较的精确数值来取最小。上述优化采用标准乘法的标量操作数 abc；若只知道某黑盒耗时 O(abc) 而不知道具体成本，能优化的是该成本模型，不能保证实际机器耗时绝对最小。官方公式中的 O(abc) 应按这个模型理解。

Problem 4：最长递增子序列（答案 p.2–3）

定义 L[i] 为“必须以 A[i] 结束”的最长严格递增子序列长度，而不是前缀全局最优。因为要决定 A[i] 能接在哪个元素后面，需要知道前一段的最后数值。

初始化 L[i]=1、prev[i]=空。按 i 递增，枚举 j<i 且 A[j]<A[i]；若 L[j]+1 更大，就更新 L[i] 与 prev[i]=j。没有合适 j 时单独 A[i] 是长度 1 的可行序列，不能对空集合直接取 max 而忘记基例。

正确性：最优序列若不止一个元素，其倒数第二个位置必为某个合法 j；删去 A[i] 后必须是以 j 结束的最优序列，否则替换成更长者可改进原解。枚举所有 j 恰好覆盖所有可能。

原题数组 [10,5,20,17,3,30,25,40,50,60,24,55,70,58,80,44] 对应长度表为 [1,1,2,2,1,3,3,4,5,6,3,6,7,7,8,5]。最大值 8 在第 15 项，可恢复 10,20,30,40,50,60,70,80。最后一项只给长度 5，所以不能直接返回 L[n]。双重扫描 O(n²)，数组 O(n)，恢复 O(n)。

补充：为什么“以 i 结束”比“前 i 项最长”多保留了关键信息。 自取前缀 [1,10,2]，全局LIS长度为2，但长度2的实现既可结束于10，也可结束于2；若下一个数是3，只有结束于2的那一条能接上。单独保存一个数字2，不告诉末项，无法判断可否延伸。当前状态按每个结束位置分别存值，正是保留这份信息，再在最后对结束位置取max。

自测：数组 [2,2,3] 的严格递增长度是多少？若改成不下降又是多少？

严格递增只可取一个2后接3，长度2，前驱条件必须是小于；不下降可以取三个数，长度3，条件改成小于等于。条件变化会改变所有可用转移，不只是最后输出时去掉重复。

Problem 5：最大子数组的线性 DP（答案 p.3–4）

令 E[i] 为必须在 i 结束的最大非空连续子数组和。这样的子数组只能是单独 A[i]，或某个以 i−1 结尾的子数组再接 A[i]。在后一类中取最优前缀，得到

E[1]=A[1],\qquad E[i]=\max\{A[i],E[i-1]+A[i]\}.

同步记录当前段起点：若选择 A[i] 就设 start=i，否则保留旧 start。再维护全局最大值及其左右端点。每轮常数工作，O(n) 时间、O(1) 额外空间；输入数组本身另计。

原题数组 [13,-3,-25,20,-3,-16,-23,18] 的 E 值为 [13,10,-15,20,17,1,-22,18]，全局最大 20，区间是第 4 项单独 [20]。当上一段贡献非正，丢掉它不会更坏；为正则继续接上才有益。

全负数组 [-5,-2,-8] 的答案是 -2，不是 0，因为不允许空子数组。全局 best 应从 A[1] 初始化。E[i−1]=0 时，续接与重新开始都可能最优；选一种固定规则即可，不应误写成续接一定更差。

来源与证据

本组官方题目与答案 p.1–4；数值表已独立计算核对。本文不据练习推断考试范围。