COMP3121 Week07 学习笔记

SCS：构造方法、例子与最优性

最短公共超序列（Shortest Common Supersequence, SCS）要找一条尽量短的新序列，让 A、B 都能作为它的子序列。可以跳过字符，但相对次序要保留。

做法：先求一条最长公共子序列 LCS，再沿它的匹配位置从左向右合并。每遇到一个共同字符，就先放入两串各自尚未放入的前置字符，再把该共同字符放一次；最后放入两串剩余尾部。两串内部的顺序始终不变。

设 n = |A|，m = |B|，L = LCS 的长度。
SCS 的最短长度 = n + m − L。

代价：复用第五周的 LCS 算法，时间 O(nm)，完整表空间 O(nm)；恢复 LCS 后合并两串再用 O(n+m) 时间。

编辑距离：状态定义与递推

编辑距离（Edit Distance）把 A 改成固定目标 B，并使总代价最小。允许插入、删除、替换；分别记非负代价 cI、cD、cR。B 是目标，下面的操作都作用在当前 A 上。

E(i,j) = 把 A[1..i] 变成 B[1..j] 的最小总代价。
i、j 是两个前缀的长度，允许为 0。

E(0,0) = 0
E(i,0) = i × cD       // 删完 A 的 i 个字符
E(0,j) = j × cI       // 从空串插入 B 的 j 个字符

教授从“目标末尾 B[j] 怎样被对应”解释递推：它可以对应 A[i]，也可以对应 A 中更早的字符，或者对应一个新插入的字符。于是只需处理一步，就能回到同一形式的较短前缀问题。

当 i,j ≥ 1：
δ = 0（A[i] = B[j]），否则 δ = cR。
E(i,j) = min(
    cD + E(i−1,j),
    cI + E(i,j−1),
    δ  + E(i−1,j−1)
)

编辑距离：填表顺序与回溯

行 i 表示 A 的前缀长度，列 j 表示 B 的前缀长度。当前格只依赖“上、左、左上”。先填基础行和列，再按行从上到下、每行从左到右填。最后答案是 E(n,m)。

自写示例：cat → coat，三种操作代价均为 1。E(1,2) 对应 c → co，插入 o 只需 1；最终 E(3,4)=1。

时间：共 (n+1)(m+1) 个状态，每个比较常数个候选，为 O(nm)（两串非空时）；包含空串的统一写法为 O((n+1)(m+1))。完整表空间同阶。恢复操作时为每格记录获胜选择，再从 (n,m) 回到 (0,0)。

矩阵链：乘法代价与问题定义

本题决定矩阵相乘的括号位置。矩阵的前后顺序固定；结合律允许 A(BC)=(AB)C，交换 A、B 的位置通常不合法。要最小化的是标量乘法次数，不是把 n 个矩阵连成一个时固定需要的 n−1 次矩阵合并。

A 是 m×q，B 是 q×p：
AB 是 m×p。
AB 的每个元素要做 q 次标量乘法，共 m×p 个元素。
所以一次矩阵合并的标量乘法数 = m×q×p。

教授让大家记住的基础事实就是“外维度 × 共同维度 × 外维度”。先选出括号方案，再按这个规则累计每次合并的代价。DP 本身只处理这些尺寸和代价，无需真的存储或乘出矩阵元素。

查看课件原图 · 实际 p66

矩阵链：从前缀改为区间状态

先试 F(j)=计算 A₁…Aⱼ 的最少代价。若最后一次合并发生在 Aₖ 与 Aₖ₊₁ 之间，左块 A₁…Aₖ 的答案是 F(k)，但右块 Aₖ₊₁…Aⱼ 也需要一个最优答案；它不是从 A₁ 开始，F 没有保存它。

改用区间状态：
C(i,j) = 计算 Aᵢ₊₁ Aᵢ₊₂ … Aⱼ 的最少标量乘法数。
0 ≤ i < j ≤ n；左端不含 i，右端包含 j。

在 i < k < j 处切开：
左块 (i,k]，右块 (k,j]，都属于同一类区间子问题。

例如 C(3,8) 处理 A₄…A₈。四个切点 k=4,5,6,7，分别依赖 C(3,k) 与 C(k,8)。区间中不允许跳过矩阵，因此这里的 contiguous subsequence 是连续的一段。

矩阵链：递推、计算顺序与恢复

用上一节的 C(i,j)。左块合并后的尺寸一定是 sᵢ×sₖ，右块一定是 sₖ×sⱼ；它们的最终尺寸与各自内部怎样加括号无关。这使左右两块可以各自求最优，再独立合并。

基础：C(i,i+1) = 0                 // 一个矩阵无需合并

当 j−i > 1：
C(i,j) = min_{i<k<j} [ C(i,k) + C(k,j) + sᵢsₖsⱼ ]

最终答案：C(0,n)。

顺序：按区间长度 ℓ=j−i 从 1 增加到 n。左右块长度都严格小于 ℓ，所以依赖已经完成。课件表格上，C(i,k) 在当前格左边，C(k,j) 在当前格下方；按普通“从上到下逐行”会先遇到未算出的下方依赖。

查看课件原图 · 实际 p72

矩阵链：括号计数与复杂度

矩阵链有 O(n²) 个区间，每个区间尝试 O(n) 个切点，因此标准算法时间 O(n³)，空间 O(n²)。教授进一步提出：短区间只有少量切点，精确求和能否把次数降到严格低于三次？

还可以把一次切点尝试看成选择三个严格递增的边界 i<k<j；从 n+1 个边界中选三个，正好得到同一个组合数。这是对当前逐个枚举切点算法的分析。

计数括号方案（不是求最便宜的方案）：
T(1) = 1
T(n) = Σ[k=1..n−1] T(k) × T(n−k)

n = 1,2,3,4,5 时，T(n) = 1,1,2,5,14。
T(n) = Catalan(n−1)。

为什么这里相乘再相加？固定最后切点，左右可以独立选择括号方案，所以相乘；最后切点不同代表互斥情况，所以相加。教授指出：计数只与链长有关，不需要两个端点；求代价则取决于具体尺寸，必须保留区间位置。

表达式括号化：同时维护最小值与最大值

固定数字和 +、−、× 的先后次序，只改变括号，使表达式结果最大。仍然枚举最后一次运算的位置，但“左右都取最大”只对加法安全：减法希望左大右小，乘法还会受到正负号影响。

下面是课件 p74 留作练习的完整补充解法。设数字是 x₁…xₙ，opₖ 是 xₖ 与 xₖ₊₁ 之间的运算符；Lo(i,j)、Hi(i,j) 分别是连续子表达式 xᵢ…xⱼ 的最小、最大可达值。这里改用两端都包含的区间 [i,j]。

基础：Lo(i,i) = Hi(i,i) = xᵢ。

对每个切点 i ≤ k < j，令：
Lmin=Lo(i,k)，Lmax=Hi(i,k)
Rmin=Lo(k+1,j)，Rmax=Hi(k+1,j)

opₖ = +：候选最小 Lmin+Rmin；候选最大 Lmax+Rmax。
opₖ = −：候选最小 Lmin−Rmax；候选最大 Lmax−Rmin。
opₖ = ×：计算四个积
    Lmin×Rmin，Lmin×Rmax，Lmax×Rmin，Lmax×Rmax；
    它们的最小、最大分别是该切点的候选。

Lo(i,j) = 所有切点候选中的最小值。
Hi(i,j) = 所有切点候选中的最大值。

按长度 j−i+1 递增计算。最终答案 Hi(1,n)。O(n²) 个区间，各尝试 O(n) 个切点、每次常数个运算，时间 O(n³)，空间 O(n²)。保存切点及用了哪两个极值状态，即可恢复括号。

树上 DP：根、子树与后序遍历

先任取一个根 r，定义 Tᵥ 为 v 及其全部后代组成的子树。每个顶点向孩子取答案，再合成为自己子树的答案；叶子是最小子问题，整棵树的答案在根处取得。

同一父亲的孩子子树彼此不重叠，适合独立组合。父节点的整个子树又包含孩子子树；同一个孩子状态可以被父节点的不同候选重复使用。要保存什么信息，取决于父节点怎样与子树连接。

计算顺序：后序 DFS（post-order DFS）
visit(v, parent):
    对每个不是 parent 的邻居 u：visit(u, v)
    用所有孩子的结果计算 v

叶子先处理，父亲后处理。

这段是帮助理解的自写流程，实际题目算法可直接用文字说明后序遍历。在无向树的 DFS 中跳过父节点，才能避免沿同一条边来回走。按深度从深到浅处理也满足依赖。

树上匹配计数：状态定义与递推

匹配（matching）是一组互不共享端点的边。它可以为空，也可以只选一条边；本题要数所有匹配，不是只数边数最多的匹配。选定边 v−u 后，两端就都不能再连接其他已选边。

查看课件原图 · 实际 p77

令 children(v) 是 v 的孩子集合。
U(v) = Tᵥ 内 v 没有被匹配的方案数。
M(v) = Tᵥ 内 v 已与一个孩子匹配的方案数。
S(v) = U(v) + M(v) = Tᵥ 的全部匹配数。

叶子：U(v)=1（空匹配），M(v)=0。
整棵树答案：U(r)+M(r)。

U(v) = ∏[u∈children(v)] (U(u)+M(u))

M(v) = Σ[u∈children(v)] {
    U(u) × ∏[w∈children(v), w≠u] (U(w)+M(w))
}

教授用 4、3、5 个子树方案说明乘法：三个孩子都要作选择，共 4×3×5=60 种；若指定第二个孩子与 v 相连，只能用其中 2 个内部未匹配方案，就变成 4×2×5=40 种。

树上匹配计数：手推与线性时间优化

沿用课件的五点树：边为 a−b、b−c、b−d、d−e，取 b 为根。后序可以是 a、c、e、d、b。先看具体值，再分析每个孩子关系到底被处理几次。

7 个匹配对应：空集；4 个单边集合；{a−b,d−e} 与 {b−c,d−e} 两个双边集合。根取在其他位置，分解方式会变，最后总数仍是 7。

对每个 v，孩子数记为 dᵥ：
1. 用 dᵥ 个因子计算 P，保存 U(v)=P。
2. 对每个孩子 u，加上 U(u) × (P / S(u))，得到 M(v)。

每个点的工作为 O(1+dᵥ)。
Σᵥ dᵥ = n−1，因为除根外，每个节点恰好是一个人的孩子。
总工作 O(n + Σᵥ dᵥ) = O(n)。

教授的第二步强调：这里不需要再改算法，只需准确数操作。不能把“某个节点最多有 n−1 个孩子”乘给每个节点。课件 p80 的 O(n³) 是未优化的粗上界；直接重乘的实现用 Σ dᵥ² 可收紧到 O(n²)，复用乘积后再按全部孩子关系求和，得到 O(n)。

叶子：F(v)=0，G(v)=−∞（必须匹配却没有孩子，不可行）。
P = Σ[u∈children(v)] B(u)
F(v) = P
G(v) = max[u∈children(v)] [w(v,u)+F(u)+P−B(u)]
答案：max(F(r),G(r))。

补录起点：DAG 与拓扑顺序

有向无环图（Directed Acyclic Graph, DAG）没有沿箭头能回到起点的环。忽略方向看起来有一圈，不代表存在有向环；每一步都要服从箭头方向。

拓扑顺序（topological order）把顶点排成一列，让每条边的起点都在终点之前。一个有向图存在拓扑顺序，当且仅当它没有有向环。Kahn 算法或合适的 DFS 实现可以在 O(n+m) 时间找到该顺序，n=|V|、m=|E|。

补录的自动转写把一些 “acyclic” 识别为 “a cyclic”，把算法人名也写错了。本页按 PDF 的定义及上下文统一为 DAG、Kahn、Dijkstra、Bellman–Ford。

DAG 路径：递推、变式与复杂度

给定源点 s，要算它到每个顶点的最短路径权重。DAG 的边权可以为负：正确顺序由依赖决定，不需要像 Dijkstra 一样依靠非负边权把最小暂定距离定案。

D(t) = s 到 t 的最小路径权重。
D(s)=0；不可达的值为 +∞；空集合的 min 也记为 +∞。

对 t≠s：
D(t) = min[(v,t)∈E] [D(v) + w(v,t)]。

按拓扑顺序计算，最后返回全部 D(t)。

正确性：任一到 t 的非空路径都有最后一条边 v→t；最优路径之前的部分也可选成到 v 的最优路径。反过来，每个可达前驱都生成合法路径候选。拓扑顺序保证它们的值已求准，按顺序归纳即可。不可达顶点的全部候选仍为 +∞。

处理 t 的时间 = O(1 + indegree(t))。
Σₜ indegree(t) = m：每条边恰好给终点贡献一次。
加上拓扑排序，总时间 O(n+m)，距离与前驱空间 O(n)。

实现应按邻接边遍历，避免为每个顶点再扫描所有顶点来寻找前驱。若输入提供出边邻接表，也可按拓扑顺序向外松弛，每条边仍只处理一次。

最长简单路径在一般图里很难，而 DAG 没有环，按拓扑顺序改成 max 就能求解。对路径计数，最后一条边不同对应不同路径，故相加；两种变式仍用 O(n+m) 次基本操作。

流水线调度：分层 DAG 建模与递推

两条流水线各有 n 道工序。每道只选一条线做，完成第 k 道才能进入第 k+1 道；换线可能花时间。选出总耗时最小的路线。看成图时，每条边都向下一道工序前进，所以天然是分层 DAG。

查看课件原图 · 实际 p89

F(1,1)=s₁+a₁,₁；F(2,1)=s₂+a₂,₁。

F(1,k)=a₁,ₖ + min(F(1,k−1), F(2,k−1)+t₂,ₖ₋₁)
F(2,k)=a₂,ₖ + min(F(2,k−1), F(1,k−1)+t₁,ₖ₋₁)

按 k 递增，每轮计算同一工序的两个状态。
答案 min(F(1,n)+f₁, F(2,n)+f₂)。

最优为 12：先在线 2 做前两道，再换到线 1 做第三道。每个状态的两种前驱穷尽合法来源，取小值后加当前工序代价，按工序归纳得到最优性。2n 个状态，每个 O(1)，总时间 O(n)，保存整表 O(n)，只求值可保留前一工序的两个值。

课件把这与 Viterbi 的状态转移思想联系起来：按阶段保留“结束在某个状态的最优值”。该联系帮助识别结构，这里无需引入隐马尔可夫模型的细节。