CSCI3160 期中详细复习：从计算模型到动态规划

范围：Warm Up 1、Warm Up 2、Lec 1–9，即 DP 4 为止。Tutorial 1–6 中与这些主题有关的原理和实现也在相应章节内说明。

这门课研究两件事：怎样保证算法算对，以及怎样证明它算得足够快。递归和分治通过缩小问题来求解；贪心每次固定一个选择；动态规划保存已经求出的子问题答案。三者的区别在于如何得到答案，正确性证明则始终要把算法的每一步与原问题联系起来。

本文按讲次分章。每章中的定义、推导和算法可以直接阅读；不需要另开课件。另一份简略复习用于回顾，真题解析保留试卷题干和完整解答。

Warm Up 1：算法的时间和空间究竟在数什么

RAM 模型与基本操作

比较算法前，需要约定一次计算的成本。RAM 模型把计算机简化为寄存器、按地址访问的内存，以及一组基本指令。一个内存单元存放一个机器字，机器字有固定的 $w$ 位；内存地址也必须能用机器字表示。课件使用八个寄存器，内存地址从 1 开始。

输入存放在内存中
       │ 按地址读入
       ▼
    寄存器 ── 运算、比较、分支
       │ 按地址写回
       ▼
    内存单元

在本课模型内，读写一个机器字、复制一个值、机器字范围内的整数加减乘除、比较和跳转，都算常数次基本操作。RANDOM(a,b) 从闭区间中的整数均匀抽取一个值，也是一项基本指令。这一约定允许我们把一次数组访问或整数比较记为 $O(1)$。

常数成本适用于模型允许装进机器字的数据。 如果一个整数长到需要许多机器字，处理整个整数就不能自动算一次操作。后面的算法分析均采用课程的机器字假设。

运行时间是执行的基本操作总数。一个循环是否快，取决于执行多少轮、每轮做多少工作，以及内部是否还有递归或循环。把 $n$ 个元素复制到新数组，需要逐个读写，因而是 $O(n)$，不能因为伪代码只有一行就记成 $O(1)$。

课件把空间定义为运行中访问过的最大内存地址。对于从低地址连续使用的内存，这与使用的存储单元数量同阶。描述算法时还会区分输入空间、保存答案的空间和辅助空间；递归调用栈属于辅助空间。下文写“辅助空间”时，指输入之外额外占用的存储。

确定性算法与随机算法

确定性算法在同一输入上沿着固定的步骤运行。随机算法会使用随机数，同一输入也可能经历不同的运行过程。随机化可以用来选择接下来检查的位置，或选择划分问题的枢轴。

随机运行时间与随机正确性是两回事。 本范围中的随机选择算法始终返回正确答案，随机性影响的是它需要重试多少次。期望时间就是对这些随机运行过程的时间取平均，不代表允许算法以某个概率返回错误结果。

Warm Up 2：最坏情况、渐近界与随机重试

先明确输入规模，再比较增长速度

数组问题通常用元素数 $n$ 表示规模。图算法要分别保留顶点数 $|V|$ 和边数 $|E|$。两个字符串的问题有两个长度 $n,m$；矩阵的边长是 $n$ 时，输入本身有 $n^2$ 个元素。写复杂度前，应先明确变量代表什么。

对最终非负的函数，$f(n)=O(g(n))$ 表示：存在与 $n$ 无关的常数 $c>0,n_0$，使所有 $n\ge n_0$ 都满足 $f(n)\le c g(n)$。它给出渐近上界。$f(n)=\Omega(g(n))$ 给出相应下界；同时满足两者才是 $f(n)=\Theta(g(n))$。

这些比较只要求从某个规模开始成立。常数倍和有限个小输入不会改变渐近阶。$O$、$\Omega$、$\Theta$ 分别表示上界、下界、紧确界，它们本身不表示最坏、最好或平均情况。必须先说明分析的是哪一个时间函数，再为该函数求界。

比较增长速度时，固定底数的对数只差常数倍。对任意固定 $a,b>0$，$(\log n)^a$ 比 $n^b$ 增长慢；对任意固定 $b>0,c>1$，$n^b$ 比 $c^n$ 增长慢。相加的成本由增长较快的部分主导，嵌套执行的成本则应按实际次数相乘或求和。指数里也含 $n$ 的式子，通常先取对数，再比较指数的增长。

最坏时间与最坏期望时间

设 $T(I)$ 是确定性算法处理输入 $I$ 的时间，$\mathcal I_n$ 是所有规模为 $n$ 的合法输入，则最坏时间是

对随机算法，写成 $T(I,R)$，其中 $R$ 代表运行时的随机选择。本课所说的期望时间保证通常是

意思是：先固定任意一个合法输入，对算法自己的随机选择取期望，再保证每个输入都满足这个时间界。 这里没有假定输入是随机产生的，也不是把所有输入平均起来。

二分查找说明了确定性的最坏分析。输入数组已经有序，比较中间元素后，只保留仍可能含目标的一半。第 $t$ 次缩小后，剩余规模至多约为 $n/2^t$。当它降到常数时结束，所以比较轮数为 $O(\log n)$。这里的关键条件是有序性：它让一次比较能够排除整段位置。

独立重试为什么得到 $1/p$

一次尝试成功的概率为 $p>0$，各次尝试独立，且失败后从相同条件重新开始。令 $N$ 为直到首次成功为止的尝试总数，包含成功的那一次。第一次总要尝试；以概率 $1-p$ 失败后，还需要平均 $\mathbb E[N]$ 次。因此

一次尝试 ── 成功，概率 p ── 结束
    │
    └── 失败，概率 1-p ── 回到相同的尝试条件

首次成功之前的失败次数是 $N-1$，期望为 $(1-p)/p$。这两个量相差 1，因为是否把成功那次计入不同。

如果长度为 $n$ 的数组里恰有 $z>0$ 个零，每次均匀、独立、有放回地抽一个位置，则成功概率是 $z/n$，找到零的期望检查次数为 $n/z$。当零占固定比例时，期望检查次数是常数。某次运行仍可能连续失败很久，所以这个期望界不是每次运行的上限。

确定性检查无法获得同样的保证：当数组有一半位置为零时，对手可以把前面被检查的位置安排为非零，使算法需要检查线性多个位置。这说明随机化改善的是这一问题的最坏期望时间。

拒绝采样如何保持均匀

需要在 $n$ 个对象中均匀选择，但现有随机源能等概率产生 $M\ge n$ 个结果时，可以接受对应合法对象的 $n$ 个结果，其他结果全部重试。一次成功概率为 $n/M$，每个合法对象在一次尝试中被选到的概率都相同，因此只看被接受的结果，每个合法对象出现的概率仍相同。

如果随机源是公平随机位，令 $b=\lceil\log_2 n\rceil$，用 $b$ 位组成 $0$ 到 $2^b-1$ 的整数，只接受小于 $n$ 的结果。由于 $2^b<2n$，接受概率超过 $1/2$，期望尝试次数小于 2。每次生成 $b$ 位，所以期望成本为 $O(\log n)$；$n=1$ 时直接返回唯一对象。概率保证与生成随机数本身的成本必须分别计算。

Lec 1：递归、选择与几何级数

递归调用必须保留同一个问题的含义

递归用一个规模更小的同类问题的答案，构造当前问题的答案。写递归时，要明确输入、返回值、停止条件，以及每次调用为什么确实缩小。正确性证明则用归纳法：最小输入直接正确；假设较小输入的调用正确，再证明当前调用组合出的结果正确。

汉诺塔的递归体现了这个结构。要把 $n$ 个大小不同的盘从起点柱移到终点柱，任何时刻都不能把大盘压在小盘上。移动最大盘之前，必须先把上面的 $n-1$ 个盘移到辅助柱；移动最大盘后，再把那 $n-1$ 个盘移到终点柱。于是移动次数满足

两个较小任务都必须完成，因此递归树不断分叉。递归深度只有 $n$，却有指数多个调用。调用深度与调用总数不能混用。

第 $k$ 小元素：划分以后，目标只在一边

选择问题的输入是含 $n$ 个互异数的集合 $S$ 和整数 $1\le k\le n$，输出按从小到大排序后的第 $k$ 个数。这里只要求一个秩，不需要把整个集合排好序。

选择枢轴 $v\in S$，把元素分为

令 $r=|L|$。因为数互异，$r$ 就是 $v$ 的秩。若 $k\le r$，目标是 $L$ 中的第 $k$ 小；若 $k>r$，前 $r$ 个元素全部在 $L$，删去它们后，目标变为 $R$ 中的第 $k-r$ 小。

原集合的有序位置（用于说明秩，无须真的排序）
┌───────────────┬───────────────┐
│ L：前 r 个数  │ R：后 n-r 个数│
└───────────────┴───────────────┘
    k ≤ r：秩不变     k > r：新秩 k-r

这给出了正确的递归，但还没有给出快的递归。若每次只删去一个元素，扫描成本会累加为 $n+(n-1)+\cdots+1=\Theta(n^2)$。

随机选择：重试到留下的部分足够小

本讲的办法是随机选枢轴，检查目标所在那一部分的大小。如果这一部分超过原集合的 $2/3$，就放弃此次划分，重新抽取枢轴；否则才递归。对很小的集合直接排序返回，以免整数取整影响停止条件。

Select(S, k):
    若 |S| ≤ 5：直接排序，返回第 k 个数
    重复：
        从 S 中均匀选 v
        扫描 S，建立 L = {x ≤ v}、R = {x > v}
        若 k ≤ |L|：B = L，t = k
        否则：B = R，t = k - |L|
    直到 |B| ≤ 2|S|/3
    返回 Select(B, t)

每次划分都保持目标元素和它在保留集合中的秩，所以重试只改变运行时间，不影响答案。一旦进入递归，集合大小严格减小，因此最终到达直接处理的小集合。

当枢轴的秩落在中间约三分之一范围内时，左右两边都不会大于约 $2n/3$，无论目标在哪边都可以继续。这样的枢轴占固定正比例；整数取整不会改变“成功概率有常数下界”这一事实。因此，在规模为 $s$ 的一层中，期望只需常数次尝试，每次扫描 $O(s)$，这一层的期望工作量为 $O(s)$。

通过的各层规模至多按固定比例缩小，所以

线性时间来自“每层线性工作，加上只递归一个按比例缩小的子问题”。 不能只看递归层数是 $O(\log n)$，便把每层都按原来的 $n$ 相乘。各层实际扫描的集合越来越小。

如果已经有一个能在线性时间找中位数的确定性黑盒，可以直接用中位数划分；每次保留至多约一半，得到确定性线性时间的选择算法。这里的结论依赖黑盒本身的时间保证，不能把“找中位数”当成免费操作。

几何级数在算法分析中的含义

若每轮处理的规模至多是上一轮的 $\alpha$ 倍，其中固定 $0<\alpha<1$，每轮工作与该轮规模成正比，则总成本受

控制。固定比例是关键：$\alpha$ 不能随着 $n$ 越来越接近 1。还要数清每层有几个子问题；若同时递归两边，就应把同一层所有子问题的工作相加，下一讲的归并排序正是这种情况。

Lec 2：分治的关键是怎样合并答案

归并排序

归并排序把数组按位置分为两半，分别排好序，再把两个有序数组合成一个有序数组。合并时维护左右两个指针，每次输出当前较小的元素并移动相应指针；一边用完后，另一边剩余元素可以直接接在末尾。

左半已排序：L[1] ... L[i] ...
右半已排序：R[1] ... R[j] ...
                    │
         比较两个尚未输出的最小元素
                    ▼
             把较小者接到结果末尾

为什么只比较两个指针就足够？在各自数组内部，指针后的所有元素都不小于指针处元素。因此，两边未输出元素中的全局最小值，一定在这两个位置之一。每次输出当前最小值，最终结果便有序且不漏元素。

MergeSort(A):
    若 |A| ≤ 1：返回 A
    按位置把 A 分为两半
    L = MergeSort(左半)
    R = MergeSort(右半)
    用双指针合并 L、R，返回合并结果

合并共输出 $n$ 个元素，成本 $\Theta(n)$。两半都需要排序，所以

递归树每层所有数组的长度之和为 $n$，共有 $\Theta(\log n)$ 层。使用可复用的合并缓冲区时，辅助数组为 $O(n)$，递归栈为 $O(\log n)$。

逆序对：在合并时统计跨越分界的配对

数组 $A[1..n]$ 的逆序对是满足 $i<j$ 且 $A[i]>A[j]$ 的一对下标。它同时要求位置在前、值更大。最多有 $\binom n2=n(n-1)/2$ 对。

按原始下标分成左右两半后，每个逆序对恰好属于三类之一：完全在左半、完全在右半、左边元素与右边元素组成的跨边界配对。递归可以统计前两类，合并负责第三类。

本讲先给出一种合并方式：把左半的值排好序，对右半的每个值二分查找左半有多少元素比它大。一层做 $O(n\log n)$ 工作，总时间为 $O(n\log^2n)$。Tutorial 3 的改进是让每次递归同时返回两个结果：逆序对数量，以及该部分元素的有序数组。 上一层便不用重新排序。

设递归返回有序数组 $L,R$，当前指针为 $i,j$。若 $L[i]\le R[j]$，输出 $L[i]$，它不会与右边尚未输出的元素构成逆序对。若 $L[i]>R[j]$，则左边从 $i$ 开始的所有剩余元素都大于 $R[j]$；它们在原数组中也全部位于右半元素之前。因此，应一次增加 $|L|-i+1$ 对，再输出 $R[j]$。

左半未输出：L[i] ≤ L[i+1] ≤ ... ≤ L[末尾]
                全部 > R[j]
右半当前：      R[j]

输出 R[j] 时，新增逆序对数 = 左半剩余元素数

CountInv(A):
    若 |A| ≤ 1：返回 (0, A)
    (cL, L) = CountInv(左半)
    (cR, R) = CountInv(右半)
    i = j = 1，cross = 0，B = 空数组
    当两边均未用完：
        若 L[i] ≤ R[j]：输出 L[i] 到 B，i += 1
        否则：cross += |L|-i+1；输出 R[j]，j += 1
    把剩余元素接到 B 后面
    返回 (cL + cR + cross, B)

每一对跨边界逆序对，都在它的右端元素被输出时计入一次，其他时刻不再计入。配合左右递归结果，三类配对不重不漏。合并只扫描一次，因此总时间为 $O(n\log n)$，辅助空间为 $O(n)$。

二维支配计数：先用一个坐标确定方向

对两个不同的点 $p,q$，若 $q.x\ge p.x$ 且 $q.y\ge p.y$，称 $q$ 支配 $p$。本课要求对每个点求出它支配了多少个其他点。也就是，对固定的 $q$，统计同时位于它左侧或同一纵线、下方或同一横线的其他点。课件假设不同点的 $x$ 坐标互异。

                     y
                     ↑
    q 能支配的区域    │        q
    x ≤ q.x，y ≤ q.y ├────────●
                     │        │
                     └────────┼──→ x

先按 $x$ 递增排序，再按位置平分为 $L,R$。左半每个点的 $x$ 都小于右半每个点。因而左半点不可能支配右半点；跨边界时，只需为右半点 $q$ 统计左半中满足 $p.y\le q.y$ 的点。

与逆序对一样，本讲可以用“排序加二分”完成这一统计，得到 $O(n\log^2n)$。更快的递归让每个子问题返回按 $y$ 排序的点，并保留每个点的身份和已累计的计数。合并左右的 $y$ 序列时，维护 seenL，表示已经输出的左半点数。

合并两个按 y 排序的子结果：
    seenL = 0
    若当前左点的 y ≤ 当前右点的 y：
        输出左点；seenL += 1
    否则：
        右点的计数 += seenL；输出右点
    左边用完后，每个剩余右点也增加 seenL
    右边用完后，直接输出剩余左点

把这一合并过程放回完整递归，算法如下。每个点的 count 只初始化一次，之后保留点的身份并不断累加。

CountDominance(P):
    对每个点 p：count[p] = 0
    X = 把 P 按 x 递增排序
    Solve(X)
    返回每个点的 count

Solve(X):
    若 |X| ≤ 1：返回 X
    按 X 的位置分为两半 XL、XR
    L = Solve(XL)，R = Solve(XR)
    按 y 递增合并 L、R，同时用 seenL 为右点累加跨边界计数
    返回合并后的 y 有序序列

Solve 的输入按 $x$ 排序，返回值按 $y$ 排序。递归调用前先固定左右成员；接收一个孩子的返回结果，不会改变另一个孩子的输入。单点没有其他点可支配，基例不新增计数。

输出右点 $q$ 时，已经输出的左点恰好满足 $p.y\le q.y$。因此 seenL 正好是它在左半支配的点数。$y$ 相等时先输出左点，是为了把等号允许的配对算进去。递归内部已统计同半边的支配关系，当前层只加跨边界关系，所以不重复。

最初按 $x$ 排序花 $O(n\log n)$；后面递归每层线性合并，仍为 $O(n\log n)$。递归分界始终来自最初的 $x$ 次序，返回时按 $y$ 排序只是为了合并。 两种顺序分别承担不同作用，不能在下层随意换用 $y$ 来划分。

矩阵乘法：减少递归乘法的数量

两个 $n\times n$ 矩阵相乘，定义为

共有 $n^2$ 个输出元素，每个需要 $n$ 次乘加，直接算法为 $\Theta(n^3)$。矩阵通常按行连续存储；读写一个元素仍是常数成本，读写整个矩阵需要 $\Theta(n^2)$。

把每个矩阵分成四个等大的块，公式仍保持乘法次序。例如 $C_{11}=A_{11}B_{11}+A_{12}B_{21}$。直接分块需要八次规模为 $n/2$ 的矩阵乘法和 $O(n^2)$ 次加减，得到 $T(n)=8T(n/2)+O(n^2)=O(n^3)$，本身没有改善阶数。

Strassen 的关键是利用加减组合，把八次乘法减为七次。按本课记号定义

再组合为

这些组合如何恢复普通矩阵乘法，可以逐项验证。先看左上块：

其余三块也由同样的分配律得到：

四个结果恰好等于块矩阵乘法的定义。推导没有交换矩阵相乘的次序，只用了分配律与加减抵消。

四个 A 块、四个 B 块
          │ 先做块加减
          ▼
     七次递归矩阵乘法
          │ 再做块加减
          ▼
       四个结果块

递归到单个元素时直接相乘。各层递归满足

第 $\ell$ 层有 $7^\ell$ 个问题，每个问题的块加减成本为 $O((n/2^\ell)^2)$，该层总成本为 $O(n^2(7/4)^\ell)$。越往下成本越大，整个级数与最底层同阶，即 $n^{\log_2 7}$。若 $n$ 不是 2 的幂，可补零到下一个 2 的幂；新边长小于 $2n$，不改变渐近阶，最后取原来大小的结果区域。

Lec 3：活动选择与交换论证

要最大化的是活动数量

每个活动占用一个时间区间 $[s_i,f_i]$，任务是选出尽可能多的互不相交区间。本讲把区间当作闭区间，因此两个活动共享端点也算相交；后一个活动必须满足 $s_j>f_i$ 才能接在前一个后面。如果题目另行允许结束与开始发生在同一时刻，条件才改为 $s_j\ge f_i$。

贪心算法每次选择结束时间最早的剩余活动，删掉与它相交的活动，再对余下活动重复。结束得早，可以为后续活动留下尽可能长的时间，但这个直觉还不足以构成证明：必须说明选它不会牺牲最大活动数。

把活动按结束时间递增排序
last = -∞，答案为空
依次检查活动 [s, f]：
    若 s > last：
        选择该活动
        last = f
返回所选活动

排序后，一次扫描就能实现“选择后删除冲突活动”。被拒绝的活动开始得太早，与最后一个已选活动冲突；被接受的第一个活动，则是所有仍可选活动里结束最早的那个。排序为 $O(n\log n)$，扫描为 $O(n)$。

为什么最早结束的活动可以成为最优解的一部分

令 $g$ 为结束最早的活动。取任意一个活动数最多的可行解 $O$，按时间排列，令其中第一个活动为 $j$。由于 $g$ 最早结束，有 $f_g\le f_j$。

把 $O$ 中的 $j$ 替换成 $g$。原来排在 $j$ 后面的每个活动，都在 $f_j$ 之后开始；它们也就在 $f_g$ 之后开始，所以不会与 $g$ 冲突。替换只把一个活动换成另一个，数量不变。于是得到一个包含 $g$ 的最优解。

原最优解： [ j ]        [后续活动]   [后续活动]
换入 g ： [g]          [后续活动]   [后续活动]
             f_g ≤ f_j
后续活动仍然来得及开始，活动数没有减少

选定 $g$ 后，只考虑在它结束以后开始的活动。这又是一个相同形式、规模更小的活动选择问题。若后续部分没有取到这个子问题的最优解，就可以把它替换成活动数更多的后续安排，从而改进整体解，与整体最优矛盾。因此，对剩余活动重复同样选择可以得到最优答案。

也可以把整个证明写成一个不变式：每轮选择完成后，存在某个最优解包含当前全部已选活动。 起初显然成立；上述替换使它在每轮后继续成立。扫描结束时，每个未选活动都曾因与某个已选活动冲突而被拒绝。因此不存在与全部已选活动都相容的额外活动。那个包含已选活动的最优解无法再含其他活动，已选集合本身就是最优解。

这个结论不要求最优解唯一，也没有说每个最优解都必须包含 $g$。交换论证保证的是可以找到一个与当前选择相容的最优解。

Lec 4：最小生成树、Prim 与 Kruskal

生成树要满足什么条件

给定连通无向带权图 $G=(V,E)$，生成树使用全部顶点，用图中的一部分边使它们连通，而且不含环。生成树恰有 $|V|-1$ 条边。最小生成树 MST 在所有生成树中最小化边权之和：

它优化的是整棵树的总重量，不是从某个起点到各点的路径长度。课件采用正整数边权。以下交换证明只比较边的大小，并不依赖“权重一定为正”。若图不连通，则不存在覆盖全图的生成树，需要分别处理各连通分量。

树有两个直接用于证明的性质：删去一条树边，会得到两个连通分量；给树加入一条原本不在树中的边，会产生一个环，因为它的两个端点原先已经有唯一的一条树路径相连。

割性质：跨越两边时可以安全选最轻边

把顶点分成非空的 $S$ 和 $V\setminus S$，称为一个割。两个端点分处两边的边叫跨边。任何生成树都必须使用至少一条跨边，否则两侧无法连通。

设 $e$ 是这个割上的最轻跨边。取一棵 MST $T$。如果 $e\in T$，结论已经成立；否则，把 $e$ 加入 $T$，得到唯一的环。沿环从一侧走到另一侧后，还必须跨回来，所以环上另有一条跨边 $f$。由于 $e$ 最轻，$w(e)\le w(f)$。删去 $f$ 后重新得到生成树，且总重量不增加，因此它仍是 MST，并且包含 $e$。

       S                    V\S
   树中的一段路径 ── f ── 树中的一段路径
          ╲                    ╱
           └──── 新边 e ──────┘

加入 e 形成环；删去环上的另一条跨边 f

任意割上的最轻边，至少属于某棵 MST。 若它是该割唯一的最轻边，任何不含它的生成树都可被严格改进，因此它属于每棵 MST。这一区别来自比较是“$\le$”还是“$<$”。

Prim：不断扩展同一棵树

Prim 始终维护一棵已选出的树，顶点集合记作 $S$。每次选择 $S$ 到外部的最轻跨边，把对应的外部顶点加入 $S$。按课件采用的初始化方式，第一条边取全图最轻边；单顶点图直接返回空边集。

Prim(G):
    若 |V| = 1：返回空集
    选全图最轻边 uv
    T = {uv}，S = {u,v}
    当 S ≠ V：
        在一端属于 S、另一端不属于 S 的边中取最轻边 xy
        令 x ∈ S、y ∉ S
        T 加入 xy；S 加入 y
    返回 T

每次只接入一个新顶点，所以连通性保持，也不会产生环。图连通保证只要还有外部顶点，就存在跨边。最终得到一棵生成树。

最优性需要比单独使用割性质多说明一步：新边加入后，仍要保留此前已经选中的边。假设某棵 MST 包含当前选边。如果它还包含新边，直接继续；否则按前面的环交换删去另一条跨边。当前已选边的两个端点都在 $S$ 内，因此被删去的跨边不可能是当前已选边。于是存在一棵 MST 包含扩展后的全部选边。最终算法的边数已是 $|V|-1$，便与这棵 MST 相同。

用最小优先队列实现 Prim

直接在每轮扫描全部边，也能选出最轻跨边，但可能花 $O(|V||E|)$ 时间。更快的实现为每个外部顶点 $v$ 保存

没有相邻树内顶点时设为 $+\infty$，并用 parent[v] 记录取得最小值的树内端点。所有外部顶点放进按 key 排序的最小优先队列。

最小 key 对应全体跨边中的最轻边，因此取出这个顶点即可完成 Prim 的下一步。新顶点 $v$ 加入以后，旧的树内顶点仍在；可能让某个外部顶点 $z$ 获得更轻连接的新增候选，只有边 $vz$。所以只需扫描 $v$ 的邻接边，比较并更新相邻外部顶点的 key 和 parent。

取出 key 最小的外部顶点 v
    │
    ├── 选择 parent[v]—v
    ├── 把 v 加入树
    └── 扫描 v 的邻边 vz
            若 z 仍在树外且 w(vz) < key[z]
            更新 key[z]、parent[z] 和队列位置

实现上可用二叉最小堆，并保存“顶点编号到堆位置”的索引，使减小键值后能找到该顶点并向上调整。Tutorial 4 给出的按编号查找、插入、删除、删除最小值结构也能实现更新：找到旧项，删除后插入新项。每项操作为 $O(\log|V|)$。

每个树外顶点至多出队一次，所有邻接表的扫描次数合计为 $2|E|$，每条边至多触发常数次更新。因此总时间为

图的邻接表占 $O(|V|+|E|)$ 空间；优先队列和 key、parent 数组额外占 $O(|V|)$。这里复杂度的依据是各类操作的总数，不是把每轮都算成扫描全图。

Kruskal：连接当前不同的连通分量

Tutorial 5 的 Kruskal 从没有边的森林开始，每个顶点自成一组。把边按权重递增排序，依次检查：如果一条边的两端属于不同分量，就选它并合并两个分量；如果已经属于同一分量，就跳过，否则会形成环。选满 $|V|-1$ 条边后结束。

Kruskal(G):
    把所有边按权重递增排序
    每个顶点建立一个独立集合；T = 空集
    依次检查边 uv：
        若 Find(u) ≠ Find(v)：
            T 加入 uv
            Union(u,v)
    返回 T

Find 查询顶点所属集合，Union 合并两个集合。一个简单而足够的实现是并查集按大小合并：让较小树的根指向较大树的根。当一个顶点的深度增加时，它所在集合的大小至少翻倍，所以深度最多 $O(\log|V|)$。因此无需依赖更复杂的优化，也能保证每次查询和合并为 $O(\log|V|)$。

为什么当前被接受的边是安全的？取它一端所属的当前分量 $C$。算法已按权重检查过更轻的边；若存在更轻的边跨出 $C$，它在被检查时也连接两个不同分量，本应已经被接受，使两端如今同属一个分量，产生矛盾。因此当前边是割 $(C,V\setminus C)$ 上的一条最轻边。

用相同的交换论证，可以让某棵 MST 包含新边而保留此前全部选边：此前选边都位于当前分量内部，不会是交换时删除的跨边。由此归纳得到 Kruskal 的最优性。排序花 $O(|E|\log|E|)$，并查集操作合计 $O(|E|\log|V|)$；对连通图，总时间为 $O(|E|\log|E|)$。

环性质与唯一性

若一条边是某个环上唯一最重的边，则它不属于任何 MST。假设某棵 MST 含有它，删除它后得到一个割；原环上还有另一条边跨越这个割，而且严格更轻。换入该边会降低总重量，与最优性矛盾。

若最重权重存在并列，交换只保证总重量不增加，此时只能保证可以找到不含某条指定最重边的 MST，不能断言所有 MST 都排除它。

当全图边权互异时，MST 唯一。若存在两棵不同 MST，取它们边集差异中最轻的边 $e$，设它属于第一棵。把 $e$ 加入第二棵所产生的环中，必有一条不属于第一棵的边 $f$；否则第一棵本身也会含环。由于权重互异且 $e$ 最轻，$w(e)<w(f)$，交换会严格改进第二棵，矛盾。互异边权是唯一性的充分条件，存在相同权重并不自动意味着 MST 不唯一。

Lec 5：Huffman 编码为什么合并最小频率

前缀码与要优化的代价

一个二进制编码为每个字符分配一个由 0、1 组成的码字。前缀码要求：任意字符的码字，都不是另一个字符码字的前缀。这样，读入一串连续的编码位时，一旦读到某个完整码字，就可以立即确定一个字符。

把全部码字从根开始逐位插入一棵二叉树，相同的位前缀共享路径。前缀条件保证某个码字结束的位置不会还有其他码字继续向下延伸，所以所有字符都落在叶子上。反过来，只在二叉树叶子上放字符，也不会让一个码字成为另一个的前缀。因此，前缀码与这样的编码树相对应：从根出发，左边标 0、右边标 1，字符只放在叶子。根到某个叶子的边标签组成该字符的码字，码长等于叶子深度。

             根
          0 /  \ 1
           /    \
       子树      子树
        │         │
      字符叶子  字符叶子

根到叶子的路径 = 码字；路径边数 = 码长

设字符 $i$ 的出现概率为 $p_i$，$\sum_i p_i=1$，码长为 $d_i$。平均码长是

频率较高的字符对平均长度影响更大，因此理想编码会给它较短的码字。如果输入给的是出现次数 $f_i$，则最小化 $\sum_i f_i d_i$ 与最小化平均长度完全相同，因为总次数 $\sum_i f_i$ 是固定的。

构造算法

开始时，每个字符各自是一棵只有一个叶子的树，树的权重就是字符频率。每次取权重最小的两棵树，把它们接到一个新父节点下面；新树的权重为两者权重之和。把新树放回候选集合，直到只剩一棵树。

Huffman(字符及频率):
    为每个字符建立叶子，并按频率放入最小堆
    当堆中树的数量大于 1：
        x = 删除最小项
        y = 删除最小项
        建立父节点 z，权重为 weight[x] + weight[y]
        z 的两个孩子为 x、y
        把 z 放回堆
    返回唯一剩下的树

每次合并后，候选树减少一棵，所以共有 $n-1$ 次合并。建堆可在线性时间完成，每次删除和插入为 $O(\log n)$，总时间为 $O(n\log n)$，树和堆占 $O(n)$ 空间。左右孩子可以互换，并列频率也可有不同选择，所以最优编码通常不唯一。

最小频率的两个字符为什么能放在一起

以下讨论至少两个字符、每个字符频率为正的课堂情形。一棵最优编码树不需要只有一个孩子的内部节点：删掉这种节点，可以把下面所有叶子的深度减 1，且仍是前缀码，平均长度会下降。因此可取一棵每个内部节点都有两个孩子的最优树。

取这棵树中一个最深叶子。它的兄弟也必须是叶子，否则兄弟下面会有更深叶子。于是存在一对处于最大深度的兄弟叶子。

令 $x,y$ 为频率最小的两个字符。如果它们还不在这两个位置上，就把它们与占据这些位置的字符交换。对两个频率 $f_x\le f_a$、深度 $d_x\le d_a$，让低频字符移到深处、高频字符移到浅处，代价变化为

所以交换不会增加总代价。依次安排两个最小频率字符后，可以得到一棵最优树，其中 $x,y$ 恰好是最深处的一对兄弟。证明需要的是存在这样一棵最优树，而非所有最优树都长成这样。

合并后为什么仍是同一个优化问题

把兄弟叶子 $x,y$ 收缩成一个叶子 $z$，令 $f_z=f_x+f_y$。若 $z$ 在收缩后的树中深度为 $d$，展开后 $x,y$ 深度都为 $d+1$，所以展开增加的代价为

这个增量与其余树的结构无关。因此，原树最优当且仅当相应的收缩树最优：若收缩后还可改进，改进后展开便能改进原树。两个字符时，两者分别在根的两个孩子上，各用一位，已经最优。对更多字符，算法合并最小频率的两个字符后，把新叶子与其余字符一起放回同一个最小堆；接下来的操作正是在较小字母表上运行 Huffman。归纳假设保证它得到最优收缩树，再展开这对叶子，就得到原问题的最优树。

Lec 6 / DP 1：为什么递归会重复做同一件事

调用树与子问题集合

递归函数的不同调用，可能在计算同一个输入。只沿着每次调用继续展开，会把同一个子问题算很多遍。动态规划把“这次调用从哪里来”与“这个子问题的答案是什么”分开：只要子问题由相同状态完全确定，就能共享一个已经算出的答案。

考虑课件中的一维递推，$A[i]$ 是固定输入：

计算 $f(k)$ 时，会调用 $f(k-1),f(k-2),\ldots,f(0)$。其中 $f(k-1)$ 又要调用 $f(k-2)$ 等状态。单独看递归树，重复出现的节点越来越多；但所有不同状态实际上只有 $0,1,\ldots,k$。

递归调用关系：                 保存后的依赖关系：
      f(k)                         f(0)
     /    \                          ↓
 f(k-1)  f(k-2)                    f(1)
    /        ...                     ↓
 f(k-2)                         ... 同一状态只算一次

朴素实现的调用数量满足 $C(k)=1+\sum_{j=0}^{k-1}C(j)$，且 $C(0)=1$。比较相邻两个式子得到 $C(k)=2C(k-1)$，所以调用数为 $2^k$。重复状态才是这里指数成本的来源。

记忆化与自底向上

记忆化仍按递归顺序求值，但为每个状态增加“是否算过”的标记。第一次遇到状态时完整计算并保存，之后直接返回缓存。不能用某个合法答案值冒充“未计算”，否则答案恰好等于该值时会混淆。

自底向上则先确定依赖顺序：$f(k)$ 只依赖编号小于 $k$ 的状态，因此先算 $f(0)$，再算 $f(1),\ldots,f(n)$。计算每个新状态时，所需旧答案已经存在。

f[0] = 0
对于 k = 1, 2, ..., n：
    f[k] = -∞
    对于 i = 1, 2, ..., k：
        f[k] = max(f[k], A[i] + f[k-i])
返回 f[n]

两种方式使用相同的数学递推。记忆化只访问真正需要的状态，但需要递归栈；自底向上明确控制填表顺序，不需要递归调用。这里所有 $n+1$ 个状态都要使用，故两者都做

次候选比较，存表需要 $O(n)$ 空间。动态规划的时间是不同状态的总计算成本，不是状态数本身。 状态数为 $O(n)$，每个状态仍要枚举多种选择，所以本题不是线性时间。

Lec 7 / DP 2：钢条切割的状态、转移与方案恢复

从完整方案中分离第一段

给定长度 $n$ 的钢条，以及每个整数长度 $i$ 的售价 $P[i]$。钢条可以切成正整数长度的若干段，每段按自身长度出售。基本问题没有切割费用，要求全部钢条卖出后的最高收入。

定义 $R[k]$ 为长度恰好为 $k$ 的钢条所能获得的最高收入，空钢条没有收入，因此 $R[0]=0$。取任意一个合法切割方案，观察从左端开始的第一段，设它长 $i$。这一段贡献 $P[i]$，剩余长度为 $k-i$。第一段的位置一旦确定，剩余部分就是同样的钢条切割问题。

整根长度 k
┌────────────┬──────────────────────┐
│ 第一段 i   │ 剩余长度 k-i         │
└────────────┴──────────────────────┘
   收入 P[i]     最高收入 R[k-i]

如果一个整体最优方案的剩余部分没有取得 $R[k-i]$，就可以只替换剩余部分，得到更高的整体收入。因此有

这个等式的两个方向都要成立。一方面，任何方案都有一个第一段 $i$，它的收入不超过 $P[i]+R[k-i]$，所以不超过右侧最大值。另一方面，选择使右侧达到最大的 $i$，并接上剩余长度的最优方案，确实能得到右侧的收入。所以右侧既是上界，也能够实现。

枚举包含 $i=k$，这对应整根直接出售，收入为 $P[k]+R[0]=P[k]$。如果漏掉这一项，就错误地强制钢条至少切一次。

完整算法与复杂度

RodCut(P, n):
    R[0] = 0
    对于 k = 1, ..., n：
        R[k] = -∞
        对于 i = 1, ..., k：
            value = P[i] + R[k-i]
            若 value > R[k]：
                R[k] = value
                first[k] = i
    返回 R[n] 和 first

按长度递增计算，是因为转移使用的 $k-i$ 总小于 $k$。在计算 $R[k]$ 时，归纳假设保证所有较短长度的表值正确；刚才的递推证明再保证当前表值正确。因此最终返回的是整个问题的最优收入。

第 $k$ 个状态枚举 $k$ 个第一段长度，总时间为 $\Theta(n^2)$。R 和 first 各有 $n+1$ 项，辅助空间为 $O(n)$。同一收入可能由多种切法获得；算法只保留其中一种，不影响最优值。

从表中还原切割方案

first[k] 记录的是长度为 $k$ 的最优方案中选定的第一段长度。恢复时从剩余长度 $r=n$ 开始，输出 first[r]，再令 $r\leftarrow r-\mathrm{first}[r]$，直到 $r=0$。

剩余长度 r
    │ 输出 first[r]
    ▼
剩余长度 r-first[r]
    │ 继续读取该状态记录的第一段
    ▼
    0

每次输出的长度至少为 1，因此最多输出 $n$ 段。first 所记录的选择都达到了对应状态的最大值，逐步跟随它们，便能恢复达到 $R[n]$ 的方案。没有必要在每次更新状态时复制整份切割列表；复制列表会给计算增加额外成本，记录一个选择就足够。

Lec 8 / DP 3：按照依赖关系安排计算

状态的含义决定它能依赖什么

动态规划中的状态必须包含确定答案所需的全部信息。若两种情形被写成同一个状态，它们的可行选择和最优值就必须一致；否则复用缓存会把不同问题的答案混在一起。

转移式确定以后，可以画依赖图：每个状态是一个节点，若计算 $B$ 需要 $A$ 的值，就画 $A\to B$。箭头指向使用旧答案的新状态。填表顺序必须让每条箭头的起点先于终点出现，这种顺序称为拓扑序（topological order）。存在拓扑序的前提是依赖图无环；若状态互相循环依赖而没有另外的求解办法，就不能直接按这套填表方法计算。当前范围的递推都通过更短长度或更小下标保证无环。

一维钢条问题按剩余长度递增即可。二维前缀问题则常依赖左方、上方或左上方：

f(i-1,j-1) ──→ f(i,j)
f(i-1,j)   ──→ f(i,j)
f(i,j-1)   ──→ f(i,j)

当前格依赖的格子都必须已经计算完成

只要行、列下标都按递增方向推进，逐行或逐列计算都可满足这种依赖。不能只根据“通常从左到右”决定顺序，要检查递推真正读取哪些状态。

区间状态为什么常按长度填表

另一类状态用区间两端 $l,r$ 表示问题。若一个区间只依赖其中更短的区间，按左端点递增并不一定可行，因为所需的右侧子区间可能还没算。应先计算长度最短的边界，再依次处理更长的区间。

长度 1：所有单点区间
长度 2：所有相邻两点区间
长度 3：所有三个位置的区间
   ...
长度 n：完整区间

区间转移若枚举切分点，还必须明确切分点的合法范围，以及最短区间在没有合法切分点时的值。不能把一个空集合上的最小值或最大值当成已经定义的答案。边界状态来自问题本身，与填表顺序一起构成一个可执行的算法。

什么时候能丢掉旧状态

只要某个状态以后不会再被读取，它占用的空间就可以复用。判断依据是依赖关系，而非“动态规划一般能滚动数组”。

若二维表的一行只依赖上一行和当前行已经计算的部分，就可只保留这两行；换行时交换缓冲区。钢条切割的 $R[k]$ 则可能读取所有 $R[0..k-1]$，所以不能同样只保留最近两个值。

还要区分两个输出要求：求最优值，和恢复完整方案。最优值可能只需要少量旧状态；恢复路径却可能需要很早之前的选择记录。如果把这些信息丢掉，就要通过额外存储或重新计算才能恢复。下一讲的 LCS 会具体使用这一区别。

Lec 9 / DP 4：最长公共子序列

子序列保留顺序，但不要求连续

给定字符串 $X=x_1\cdots x_n$ 和 $Y=y_1\cdots y_m$，子序列可以删除任意位置的字符，剩下字符的相对顺序不变。子串要求连续，子序列没有这个要求。最长公共子序列 LCS 要找一个同时是 $X,Y$ 子序列的最长字符串。

一份公共子序列可以表示成若干匹配位置

其中 $i_1<\cdots<i_t$、$j_1<\cdots<j_t$，且每对满足 $x_{i_s}=y_{j_s}$。两侧下标都递增，意味着匹配连线不能交叉，也不能重复使用同一位置。

X： ... x[i₁] ... x[i₂] ... x[i₃] ...
          │          ╲          ╲
Y： ... y[j₁] ....... y[j₂] ..... y[j₃] ...

每一对字符相等，两行中的匹配位置都从左向右递增

用两个前缀定义状态

定义 $D[i,j]$ 为 $X[1..i]$ 与 $Y[1..j]$ 的 LCS 长度。这里 $i,j$ 都允许为 0，表示空前缀。任意字符串与空串的公共子序列只能为空，因此

剩下的问题是：怎样根据最后一个字符 $x_i,y_j$，把当前两个前缀归结为更短的前缀？

最后两个字符相等时

若 $x_i=y_j$，可以把这个共同字符接在 $X[1..i-1]$ 与 $Y[1..j-1]$ 的任一公共子序列后面，所以至少能得到长度 $D[i-1,j-1]+1$。

还需要证明不会漏掉更好的方案。取当前前缀的一份 LCS。如果它完全没用到 $x_i$ 或 $y_j$，就能在末尾再加上这对相等字符，得到更长的公共子序列，矛盾。如果它只用了其中一个末尾位置，这个位置一定属于最后一对匹配；把另一端也移到相等的末尾字符，所有此前匹配仍保持在它之前，长度不变。如果两侧末尾都被使用，它们必须互相匹配，否则会造成顺序交叉。

因此，总能找到一份最优解，让 $x_i,y_j$ 作为最后一对。去掉这对后，剩余部分位于两个较短前缀中，最多长 $D[i-1,j-1]$。上下界相同，得到

最后两个字符不相等时

若 $x_i\ne y_j$，它们不能互相匹配，也不能各自与对方更早的位置同时匹配，否则两对连线会交叉。因此，任一公共子序列至少舍弃这两个末尾位置之一。

舍弃 $x_i$ 后，答案至多为 $D[i-1,j]$；舍弃 $y_j$ 后，答案至多为 $D[i,j-1]$。反过来，这两个较短前缀的公共子序列仍然都是原前缀的合法公共子序列。因此

完整转移为

每个分支都来自对全部合法方案的分类，并且每个候选都能实现。这才使取最大值成为一个有依据的递推。

填表、恢复与空间压缩

LCSLength(X, Y):
    将 D 的第 0 行、第 0 列置为 0
    对于 i = 1, ..., n：
        对于 j = 1, ..., m：
            若 X[i] = Y[j]：D[i,j] = D[i-1,j-1] + 1
            否则：D[i,j] = max(D[i-1,j], D[i,j-1])
    返回 D[n,m]

计算当前格时，上方、左方和左上方均已计算。对 $i+j$ 归纳，边界正确，转移也正确，因此整张表正确。表有 $(n+1)(m+1)$ 个状态，每格只做常数次比较，时间为 $O(nm)$，完整表空间为 $O(nm)$。

若要输出一份 LCS，从 $(n,m)$ 回溯：字符相等时记录该字符并同时减小 $i,j$；不相等时，走向值等于当前格的上方或左方格子。两者并列可以任选。到达第 0 行或第 0 列后结束，把记录的字符逆序即可。

             当前格 (i,j)
                │
    ┌───────────┴────────────┐
    │ 字符相等               │ 字符不等
    ▼                        ▼
记录字符，走左上         走到保留当前值的上方或左方
    │                        │
    └───────────┬────────────┘
                ▼
       直到某一前缀变为空

回溯每步至少让一个下标减 1，所以最多 $n+m$ 步。相等分支每走一次，最优值减 1，并记录一个字符；其他分支保持最优值不变。这保证最终记录的字符数为 $D[n,m]$，位置也满足两个序列的顺序要求。

若只要长度，每行只需要上一行以及当前行左邻格，可以保留两行。把较短字符串放在列方向，辅助空间降为 $O(\min(n,m))$，时间仍为 $O(nm)$。这个空间界不包含保存两个输入字符串的成本。两行计算结束后，早期单元格已被覆盖，不能直接按上述方式回溯整份序列；恢复要求必须另行保留所需信息。

课件依据

本文重新依据以下原始课件编写，页码指 PDF 物理页。链接用于追溯来源，正文已展开学习所需的定义、算法和证明。

考试证据：知识范围按 Warm Up 1 至 DP 4 编写；真题与重新推导的解答单列于《MT-真题精讲与标准答案》。