COMP3121 Week05 学习笔记

01 · 本次范围与阅读路线

本次主题是动态规划（Dynamic Programming, DP）：把大问题拆成能重复利用的小问题，先求小答案，再按明确规则求大答案。重点是定义状态、说明递推为什么成立，以及怎样从状态得到原题答案。

本页使用 week5 文件夹中的 3-dp.pdf 与两份 transcript。第一份 TXT 的主要讲授在原文 L2、L80，第二份在 L2、L14、L20、L26；单行很长，以真实行号加可搜索短语定位。PDF 实际页码比页脚编号大 1。各模块来源标明 Lecture 1 或 Lecture 2，例子与补全证明另行标注。

先读第 02–04 节建立框架，再读 LIS 的状态与证明，最后把相同思路迁移到活动选择。每个演示旁都给出规则；可以随时单步、回退或重置。

02 · 汉诺塔：复用的是答案

输入是 n 个从小到大叠放的圆盘和三根柱子；输出是从第一根柱子搬到第三根柱子所需的最少移动次数。课件求的是一个数，因此可以复用相同规模的数值答案。

以 4 个圆盘为例：先把较小的 3 个搬到中间柱，把最大的圆盘移到目标柱，再把那 3 个搬到目标柱。前后两个“搬 3 个”的起点和终点不同，但柱子的名字不影响最少次数。

moves(1) = 1
moves(i) = 2 × moves(i−1) + 1    (i ≥ 2)

i          1  2  3   4   5
moves(i)   1  3  7  15  31

若把两个 moves(n−1) 都重新递归计算，调用树会反复展开相同问题，计算时间为 Θ(2ⁿ)。保存较小规模的答案后，每个规模只做一次“乘 2 加 1”，按 i=1,2,…,n 求值，课件中的算术操作次数是 Θ(n)。

偶数 k：2ᵏ = (2^(k/2))²
奇数 k：2ᵏ = 2 × (2^((k−1)/2))²

03 · DP 设计：六个部分与三个证明点

DP 把原题变成一组有明确含义的子问题。状态（state）就是“带参数的问题”：先说清这一格问什么，再决定这一格存什么。Lookup table 是保存答案的数组；状态的含义决定哪些旧答案可以用。

输入 → 定义子问题 → 求出基础情况
     → 按依赖顺序使用递推并保存答案
     → 提取原题答案

教授称 DP 为 efficient brute force：在所定义的转移中考虑所有合法选择，同时复用已经算好的子答案。贪心只保留局部选择，因而需要说明为何舍弃其他选择仍然安全；DP 的证明重点是转移是否完整、合法，子答案能否支持后续组合。

分治的典型例子是归并排序：两半各自排序，再合并。DP 的典型效率来源是重叠子问题。仅仅写了递归，并不能保证相同问题只计算一次。

课程默认采用自底向上（bottom-up）：先基础情况，再逐渐求较大状态。自顶向下（top-down）实现也可行，但必须缓存已求答案；记忆化（memoization）指的就是这种缓存。

本次课件按两种代价分类：一参数、常数递推（one parameter, constant recurrence）表示每个状态只查询固定个数的旧答案，如汉诺塔与跳格；一参数、线性递推（one parameter, linear recurrence）表示每个状态可能扫描线性数量的候选，如 LIS 与活动选择。这里“常数 / 线性”说的是求一个状态的工作量，不是原题答案大小（目录见 PDF p18、p23）。

04 · Hopscotch：按最后一步分组计数

输入为终点格 n，每次只允许向前走 1 格或跳 2 格；输出从 0 到 n 的不同动作序列数量。同一组动作的顺序不同，可能形成不同方案，例如 1,2 与 2,1。

先看 n=3：三种方案是 1+1+1、1+2、2+1。按照最后一步分类，“以 1 结束”的两种方案来自到达 2 的方案，“以 2 结束”的一种方案来自到达 1 的方案。

ways(i) = 从 0 到 i 的动作序列数量     (0 ≤ i ≤ n)
ways(0) = 1
ways(1) = 1
ways(i) = ways(i−1) + ways(i−2)        (i ≥ 2)

证明递推：每个到达 i 的方案，最后一步必然是 1 或 2，因而没有遗漏。两类的最后一步不同，因而不会重复。删去最后一步又能唯一恢复此前的方案，所以两类数量恰好分别为 ways(i−1) 和 ways(i−2)，相加即可。

课件 p21 把子问题范围印为 1≤i≤n，老师口头修正为 0≤i≤n，以包含 ways(0)。本页采用修正后的范围。

05 · LIS：先固定结尾，再寻找前驱

最长递增子序列（Longest Increasing Subsequence, LIS）保留原数组中的先后顺序，可以跳过元素，选出值严格递增的序列。原数组不能排序；排序会改变问题允许的先后顺序。

课件例子 A=[15,11,13,16,12,17,18,14] 中，可以选 [11,13,16,17,18]，长度为 5。子序列（subsequence）可不连续；连续的一段通常叫子数组（subarray）。严格递增要求 <，相等元素不能直接相接。

自然的初稿状态是“前 i 项的 LIS 长度”。老师指出，它没有告诉我们最优序列最后选了谁，因此单凭这一数字难以判断是否能接入新元素。

len(i) = A[1..i] 中，必须以 A[i] 结尾的 LIS 长度

合法前驱 j 的条件：
    1 ≤ j < i          保持原数组中的先后顺序
    A[j] < A[i]        保持值严格递增

len(1) = 1
len(i) = 1 + max({len(j) : 1 ≤ j < i 且 A[j] < A[i]} ∪ {0})

公式中的 1 对应当前元素 A[i]。对每个合法前驱 j，使用以 A[j] 结尾的最长序列，再接 A[i]；从这些候选中选长度最大者。写入 {0} 使没有前驱时也有明确结果：只选 A[i]，长度为 1。

为什么对每个 j 只需最长的一条？所有以 A[j] 结尾的合法序列，都能在相同条件下接上 A[i]，而接上之后都只增加 1。较短者不会优于较长者，这正是可以复用最优子答案的理由。

课件 p32 提出 O(n log n) 的改进。老师只提到高级数据结构或换一种视角后使用二分搜索，没有在本次 transcript 中推导；这里保留为课堂提及，不展开新算法。

06 · LIS：证明与恢复实际序列

本节证明上一节的状态确实得到最优长度，再说明怎样返回元素序列。以下论证对应课件 p28 的思路；严谨归纳形式放在补充展开中，包含空前驱的边界情况。

1. 基础情况：只有 A[1] 时，唯一非空子序列长度为 1，故 len(1)=1 正确。
2. 归纳前提：计算 i 时，所有 j<i 的 len(j) 都正确。
3. 合法性：对任一合法前驱 j，把 A[i] 接到以 A[j] 结尾的 LIS 后，因 j<i 且 A[j]<A[i]，得到合法递增子序列；没有前驱时只取 A[i] 也合法。
4. 最优性：任取一条以 A[i] 结尾、长度至少为 2 的最优序列，令倒数第二项下标为 m。去掉 A[i] 后，前半段必须是以 A[m] 结尾的 LIS；否则用更长的同结尾序列替换，再接 A[i]，就会得到更长的整体序列，产生矛盾。递推遍历全部合法 m，因而不会漏掉这个最优前半段。
5. 原题答案：每条非空 LIS 必然在某个下标结束，取全部 len(i) 的最大值就覆盖了所有可能终点。

恢复实际序列只需为每个 i 多存一个前驱下标 pred(i)：若最优候选来自 j，记录 pred(i)=j；若只选 A[i]，记录无前驱。前驱应是使 len(j) 最大的合法下标，不能把“下标最大”当成“长度最大”。

课件结果：
i         1   2   3   4   5   6   7   8
A[i]     15  11  13  16  12  17  18  14
len(i)    1   1   2   3   2   4   5   3
pred(i)   —   —   2   3   2   4   6   3

从最大 len 所在的下标 7 开始：
下标：7 → 6 → 4 → 3 → 2 → 无前驱
数值：18 → 17 → 16 → 13 → 11
逆序：11 → 13 → 16 → 17 → 18

顺着前驱每次下标严格减小，最多走 n 步，最后逆序得到答案，恢复时间为 O(n)。每个状态多存一个下标，空间仍为 O(n)；若每格都复制整条序列，最坏会占 O(n²) 空间。

for i = 1 to n:
    len[i] = 1
    pred[i] = 0
    for j = 1 to i−1:
        if A[j] < A[i] and len[j] + 1 > len[i]:
            len[i] = len[j] + 1
            pred[i] = j

k = any index maximising len[k]
sequence = empty list
while k ≠ 0:
    append A[k] to sequence
    k = pred[k]
reverse sequence

老师说明，写答案时应清楚交代各部分的理由，课堂的简洁归纳与替换论证已经传达核心理解。正式题目另有证明要求时，仍以该题要求为准。

07 · 活动选择：最大化总时长

这次的目标是房间被占用的总时长最大。每个活动的贡献是 fᵢ−sᵢ；它与前面贪心课里“最多选多少项”的目标不同，原有最早结束策略不能直接保证总时长最优。

先按结束时间非递减排序，使 f₁≤f₂≤⋯≤fₙ，耗时 O(n log n)。这里可以排序活动，因为原题要选活动集合，不要求保留输入列表顺序。后续下标都指排序后的活动；返回原活动身份时，排序记录中一起保留原编号。

t(i) = 前 i 个活动中，必须以活动 i 结束的兼容安排的最大总时长
t(0) = 0                       空安排；0 是哨兵，不是实际活动

t(i) = (fᵢ−sᵢ) + max({t(j) : 1 ≤ j < i 且 fⱼ < sᵢ} ∪ {0})

这与 LIS 的结构相同：固定最后一项 i，枚举倒数第二项 j，选择最好的合法前半段，再加上当前项的贡献。LIS 加 1；本题加时长 fᵢ−sᵢ。{0} 表示可以只选活动 i，也避免对虚构的 f₀ 做兼容性比较。

合法性：此前的安排本身兼容，最后一个活动 j 又满足 fⱼ<sᵢ，故接上 i 后仍兼容。此前所有活动都不晚于 j 结束，因此只需检查最后一个活动与 i 的衔接。

最优性：取任意以 i 结束的最优安排，若倒数第二个活动为 m，前半段必须是“以 m 结束”的最大总时长安排；否则替换为更好的同结尾安排，再接 i，就得到更大的总时长，矛盾。递推枚举所有合法 m，并包含只选 i 的情况，因此得到最优 t(i)。

08 · 找零：第一节 lecture 止于贪心反例

输入是整数硬币面值 d₁<d₂<⋯<dₙ 和目标金额 C，每种硬币数量不限，且 d₁=1。输出凑出恰好 C 所需的最少硬币数。1 分硬币保证每个非负整数金额都能凑出。

自然的贪心尝试是：尽量先用最大面值，再用次大面值补足。老师用课堂讨论说明，要否定这条策略，必须找到它确实比另一种方案用更多硬币的输入。

C=6 的最优值确实是 2：一枚硬币的面值都不是 6，而 3+3 可以用两枚达到 6。这个反例证明“最大面值优先”对任意面值系统不成立。

课后老师还讨论了状态设计的方向：“用 k 枚硬币能凑出的最大金额”只会得到 k 个最大面值，不能回答“恰好 C 的最少硬币数”；“是否恰好用 k 枚能凑到 C”若没有明确转移，也不足以形成算法。要同时写出参数和这个参数对应的问题。

老师提醒后续分析要关注目标金额 C。Transcript 最后几句有明显转写损坏，因此这里保留这个具体提醒；关于精确复杂度或难度分类，等后续实际讲授时再整理。

09 · 课间答疑：上一模块的两个补充

这两点来自课间对上一节贪心与图算法的答疑，放在单独的补充模块，主线仍是本次 DP。行政问题、直播故障和职业闲聊未编入算法笔记。

并查集按大小合并（Union by size）：把小分量的根挂到大分量的根。老师解释，不使用路径压缩的这种合并树中，沿父指针向上，每越过一条边，所对应的子树规模至少翻倍；从 1 到至多 n，最多经历 log₂n 次翻倍，所以高度为 O(log n)，一次查根也是 O(log n)。

增广堆（augmented heap）：普通优先队列通常只直接暴露堆顶。如果额外维护“元素目前在堆数组中的位置”，就能定位内部元素并更新其优先级；交换时同步更新位置记录。老师用这点解释此前图算法中的更新操作。

关于 DP 基础情况的答疑：从递推能处理什么反推，找出太小而无法继续使用递推的情况，再直接给出这些答案。任意多手算几项并不是定义基础情况的主要依据。

10 · 可选复习自测

以下为自写复习题，覆盖本次已讲内容。可以先记录判断，再单独展开答案；每题有清空按钮。

11 · 本 lecture 开始：找零的 DP 解法

输入是正整数面值 d₁<…<dₙ、目标金额 C≥0，每种硬币无限供应，课件假设 d₁=1。输出是恰好凑出 C 的最少硬币数。面值 1、3、4，C=6：贪心选 4+1+1 共 3 枚，最优是 3+3 共 2 枚。

不要先承诺某枚硬币最好。把金额从 0 算到 C；计算金额 i 时，枚举最后加入的一枚 dₖ，剩余金额 i−dₖ 的答案已经在表中。

opt(0) = 0
opt(i) = 1 + min { opt(i−dₖ) : 1≤k≤n 且 dₖ≤i }
按 i=1,2,…,C 计算；最终答案 opt(C)。

算 i=6 时，选 1 的候选值为 1+opt(5)=3，选 3 为 1+opt(3)=2，选 4 为 1+opt(2)=3。这里每个候选的剩余部分都用已求出的最优解，再比较所有候选。

C+1 个状态，每个最多试 n 种面值：时间 O(nC)，存数值表的空间 O(C)。若没有面值 1，需要把不可达金额设为 +∞；这属于去掉课件假设后的扩展。

12 · 伪多项式时间：数值大小与输入长度

O(nC) 对“金额数值 C”是多项式，但计算机接收到的是 C 的二进制表示。正整数 C 只需要 ⌊log₂C⌋+1 位；C=0 也只需常数位。输入没有 C 个对象，只包含 n 个面值和一个目标金额。

位数翻倍，金额可以从 C 变成约 C²，运行时间也随金额大幅增长。令 b 为 C 的位数，C 可达约 2ᵇ，因此依赖 C 的逐金额扫描不保证关于二进制输入长度是多项式。

更精确的补充：输入位数与 log(C+1)+Σ log(dₖ+1) 同阶；舍弃大于 C 的无用面值后，可用 O(n log(C+1)) 概括有效数字编码。不要把“这个 DP 不是多项式时间”写成“已经证明所有算法都不可能是多项式时间”。

13 · 回溯与 arg min：保存做了哪一个选择

opt(C) 只回答用了几枚。若要知道用了哪些面值，就在每个状态记录一个达到最优值的硬币编号 pred(i)。min 返回最小的函数值；arg min 返回使函数值最小的参数。并列最优时任选一个即可，它不表示“最小编号”。

pred(i) ∈ arg min { opt(i−dₖ) : 1≤k≤n 且 dₖ≤i }
x ← C
当 x>0：
    k ← pred(x)
    输出一枚面值 dₖ 的硬币
    x ← x−dₖ

面值按 [1,3,4] 编号，C=6 时 pred(6)=2，表示选面值 d₂=3。于是 6→3→0，输出 3、3。每次金额严格下降，能回到 0；回溯时间等于输出的硬币枚数。

14 · Integer Knapsack：可以重复拿，容量不必用满

输入是 n 类物品、正整数重量 wₖ、非负价值 vₖ 和整数容量 C≥0；每类可以拿任意非负整数次。输出是不超过容量的最大价值。正重量保证每次递推容量变小；若无限物品含零重量且正价值，目标会无界，不属于这里的递推范围。

这与找零相似，但有两处关键变化：每件增加的价值是 vₖ，目标由最少枚数变成最大价值；重量只需不超过容量，不要求恰好填满。

opt(i) = 容量不超过 i 的最大价值
若 i < minₖ wₖ：opt(i)=0，m(i)=0
否则 opt(i)=max { vₖ+opt(i−wₖ) : wₖ≤i }
m(i) 记录达到该最大值的一个物品编号。
按 i 从小到大计算；答案 opt(C)。

自写例子：A 重 2、值 3，B 重 3、值 4，容量 5。容量 1 只能空着，价值 0；容量 4 可选 A+A，价值 6；容量 5 可选 A+B，价值 7。容量 1 的 0 是允许空包，不是“重量 1 可恰好装满”。

正确性沿用找零的替换论证：最优非空组合中移走一件 k，剩余必须是容量 i−wₖ 下的最优组合，否则替换后能提高总价值。无限供应允许把 k 加回；没有可装物品时用空包。时间 O(nC)，表空间 O(C)，同为伪多项式。回溯反复输出 m(i)，并减去对应重量，遇到 m(i)=0 停止。

15 · 0/1 背包：为什么一维状态不够

现在每件物品最多取一次。若继续只存“容量 i 的最优价值”，再选物品 k 时，就不知道 opt(i−wₖ) 是否已经用过 k。自写最小反例：只有一件重 2、值 3 的物品，容量 4；旧递推得到 6，实际最多只能得到 3。

把一条最优路径回溯出来再检查，也不能修好这个状态。教授强调两种缺口：可能有另一个并列最优组合恰好不含 k；也可能所有最优组合都含 k，而合适的剩余部分必须是某个价值较低但不含 k 的组合。只保存一个最优值和一条路径，都没有保存所需的受限最优解。

直接加“禁止某一件 j”仍不闭合：接着选 k 后，剩余要同时禁止 j、k；再往下就要记录更大的禁用集合。枚举任意禁用集合会有 2ⁿ 种，容量维度再乘 C。

这里失败的是“仅按容量定义的状态”不支持所需最优子结构；不是说 0/1 背包本身无法使用 DP。状态要足够精确，让递推右侧仍然是同一类子问题。

16 · 0/1 背包：递推、证明与计算顺序

定义 opt(i,k)：容量不超过 i、只允许前 k 件物品时的最大价值。k 表示允许考虑的前缀长度，不是已经选择的件数。

opt(i,0)=0；正重量下 opt(0,k)=0
若 wₖ>i：opt(i,k)=opt(i,k−1)
否则：opt(i,k)=max(opt(i,k−1), vₖ+opt(i−wₖ,k−1))
答案：opt(C,n)。

补全正确性：任取只用前 k 件的最优解。若不含 k，它的价值不超过 opt(i,k−1)；若含 k，移除后是前 k−1 件中容量 i−wₖ 的合法组合，价值不超过相应最优值。反过来，这两个候选各自能构成合法组合，且取 k 的分支不会重复使用 k。因此两者的最大值恰好最优；k=0 的空包作为归纳基础。

两个依赖都在前一列，因此可按 k=0,1,…,n 逐列计算；只要前一列已经完整求完，当前列内的 i 可用任意顺序。也可以按 i 从小到大逐行计算，但每行必须按 k 从小到大。按容量从大到小逐行处理整张二维表，会遇到尚未计算的较小容量依赖。

自写例子：A=(重量2,价值3)、B=(3,4)、C=(4,5)，背包容量 5。前两件可选 A+B 得 7；考虑 C 后，跳过得到 7，取 C 得 5+opt(1,2)=5，所以仍选 A+B。

有 (C+1)(n+1) 个状态，每格只比较至多两个候选：时间 O(nC)，完整表空间 O(nC)。与无限背包时间形式相同，原因不同：无限背包是一维 O(C) 个状态、每格 O(n)；这里是二维 O(nC) 个状态、每格 O(1)。

恢复组合可记录选/不选；从 (C,n) 开始，不选时转到 (i,k−1)，选时输出 k 并转到 (i−wₖ,k−1)，每次 k 都减少。课件 m(i,k) 记录组合中的最大物品编号；按选/不选记方向是同一回溯思想的补充写法。

17 · 同样两维：怎样改成可以重复取

课件把这留作休息时的变式。本节直接给出补充推导：仍定义“容量 i、仅用前 k 类”，但若取了第 k 类，剩余部分依然允许继续取第 k 类。

可重复：opt(i,k)=max(opt(i,k−1), vₖ+opt(i−wₖ,k))
不可重复：opt(i,k)=max(opt(i,k−1), vₖ+opt(i−wₖ,k−1))
两式均在 wₖ≤i 时允许取物品，否则只能跳过。

关键差异是取物品分支的第二个参数。可重复时依赖同列更小容量，因此按 k 逐列计算时，列内 i 必须递增；不能照搬 0/1 背包的“列内任意顺序”。基础情况与答案保持 opt(i,0)=0、opt(C,n)，时间 O(nC)。

18 · Balanced Partition：归约到 0/1 背包

给一组正整数，每个数字按输入位置算一个独立元素，分到 A、B 两组，每个元素恰好归一组，目标是让两组和尽量接近。数字相等也仍是不同的两件物品。

T = x₁+…+xₙ
不妨令 S_A≥S_B，则 S_B≤T/2
|S_A−S_B| = (T−S_B)−S_B = T−2S_B
T 固定，因此最小化差值 ⇔ 在 S_B≤T/2 下最大化 S_B。

自写例子 [1,2,5]：T=8，容量 4。能达到的最大较小组和是 3（1+2），剩余组和为 5，最小差是 8−2×3=2。容量上限不代表一定能恰好取到 4。

正确性来自两方向的对应：任意分组可把较小组视为可行背包；任意可行背包也能与其补集组成完整分组，且背包和≤T/2。最大化背包价值正好最小化差值。构造实例 O(n)，调用 0/1 背包 O(nT)，总时间 O(nT)，仍是伪多项式。教授强调可直接说明映射并调用已知算法，不必重写全部 DP。

19 · LCS：用两个前缀定义状态

最长公共子序列（Longest Common Subsequence, LCS）要保留两个序列中共同出现且顺序一致的元素，可以跳过中间元素。例：chat 与 cart 的 LCS 是 cat，长度 3。不要混淆 substring（子串）：子串要求连续，子序列不要求连续。

只找相同字母还不够，选中的匹配必须在两个序列中都保持顺序。教授先从首字母解释后缀，再把方向反过来，用课件中的前缀状态：len(i,j) 是 A 前 i 个字符与 B 前 j 个字符的 LCS 长度。这里 i、j 是长度，0 表示空前缀。

len(i,0)=0；len(0,j)=0
若 aᵢ=bⱼ：len(i,j)=1+len(i−1,j−1)
若 aᵢ≠bⱼ：len(i,j)=max(len(i−1,j),len(i,j−1))
最终答案 len(n,m)。

末尾相同：把这个共同字符放在答案末尾，前面的部分去解两个更短的前缀。末尾不同：两个末位置不能同时被某个公共子序列使用，否则它们作为最后匹配的字符必须相同；因此至少舍弃一个，两个可能都试。两个都舍弃的情形已经包含在这些分支里，不需额外加一个候选。

按 i 递增、同一 i 内 j 递增，即字典序（lexicographic order）。当前格只依赖上方、左方或左上方：前一行已经做完，当前行左边也已经做完。若改成逐列，列内仍须从上到下，因为同列上方也可能被依赖。

共有 (n+1)(m+1) 个状态，每格 O(1)，时间 O(nm)，完整表空间 O(nm)。这里 n、m 是实际序列长度，所以与背包中的容量数值 C 有不同的输入意义。

20 · LCS 回溯：只有匹配的斜走才输出字符

求长度时顺便保存每格来自哪个方向。回溯从 (n,m) 开始：末尾匹配时沿左上走，并输出这个字符；不匹配时沿达到当前最优值的上方或左方走，不输出字符。任一坐标到 0 即停止，收集到的字符逆序后就是一个 LCS。

本表是笔记按课件示例手推的轨迹；课件 p57 的 CLRS 图使用另一对序列 ABCBDAB 与 BDCABA，同样按箭头回溯。并列时可任选一个保持最优值的方向，所以 LCS 不一定唯一。回溯至多减少 n+m 次坐标，耗时 O(n+m)。

21 · 三序列 LCS：不能先两两求解

看似自然的做法是先算 A、B 的一个 LCS，再拿这个结果与 C 求 LCS。问题是第一步丢掉了其他同样好的候选，而第三个序列可能更适合另一个候选。

正确状态是 len(i,j,k)：A 的前 i 个、B 的前 j 个、C 的前 k 个字符的 LCS 长度。三条序列原长分别为 n、m、ℓ；这里 k 是第三条前缀长度，与背包的物品前缀参数是不同用途。

任一坐标为 0：len(i,j,k)=0
若 aᵢ=bⱼ=cₖ：
    len(i,j,k)=1+len(i−1,j−1,k−1)
否则：
    len(i,j,k)=max(len(i−1,j,k),
                   len(i,j−1,k),
                   len(i,j,k−1))
答案 len(n,m,ℓ)；时间 O(nmℓ)，完整表空间 O(nmℓ)。

补全正确性：三个末尾相同时，可以把共同字符接在三个较短前缀的最优解后；任意解去掉末尾匹配后也受较短前缀最优值限制。末尾不全相同时，公共子序列不可能使用所有三个末位置，必至少舍弃一个，因此三个分支覆盖所有解；每个分支也能嵌入原三前缀。结合任一前缀为空的基础情况，可按计算顺序归纳。

按 i、再 j、再 k 递增的字典序计算。减 i 的状态在更早的外层；i 不变而减 j 的状态在更早的中层；只减 k 的状态在当前内层之前。三个末尾全匹配时的斜对角依赖也更早。并不是三维表的所有相邻格都要读，只读公式中的这四种可能坐标。