算法设计基础考点总结

资料来源：已上传的第 2–8 章 PPT 与原 Markdown 复习稿
适用范围：《算法设计与分析》期末复习
使用方式：先看“4–5星重中之重详解版”，再背“核心考点”，最后做章节练习和综合题
说明：⭐ 表示考试重要程度，⭐⭐⭐⭐⭐ 为必考级别

---

0. PPT 覆盖总清单 ⭐⭐⭐⭐⭐

章节	PPT 核心范围	复习优先级
第2章 算法分析基础	算法复杂度、渐近记号、递推关系、主方法	⭐⭐⭐⭐⭐
第3章 伸展树与跳表	字典、二叉搜索树、伸展树旋转、跳表结构与查找	⭐⭐⭐
第4章 基本搜索和遍历	BFS、DFS、时间戳、边分类、括号定理、双连通分量、关节点	⭐⭐⭐⭐
第5章 分治法	分治思想、最大最小元、二分搜索、归并排序、快速排序、选择问题、Strassen	⭐⭐⭐⭐⭐
第6章 贪心法	一般背包、作业排序、最佳合并模式、MST、Dijkstra、磁带最优存储、贪心证明	⭐⭐⭐⭐⭐
第7章 动态规划法	DP基本要素、多段图、矩阵连乘、LCS、OBST、0/1背包、备忘录	⭐⭐⭐⭐⭐
第8章 回溯法	回溯一般方法、n皇后、子集和、图着色、哈密顿环、0/1背包、批处理作业调度	⭐⭐⭐⭐

考试策略：

1. 概念题优先背“定义 + 适用条件 + 复杂度”。
2. 算法设计题必须写出：状态/选择、递推或剪枝、算法步骤、复杂度。
3. 证明题重点是：渐近记号证明、贪心正确性证明、DP最优子结构证明。
4. 模拟题重点是：Dijkstra、Prim/Kruskal、LCS表、矩阵连乘表、回溯搜索树。

---

---

4–5星重中之重详解版：先看这一部分 ⭐⭐⭐⭐⭐

本节专门补强所有 ⭐⭐⭐⭐ 与 ⭐⭐⭐⭐⭐ 内容。
目标不是“背概念”，而是让你知道：考试为什么考、题目怎么出、答案怎么写、怎么算、怎么证明。
建议复习顺序：第2章复杂度 → 第5章分治 → 第6章贪心 → 第7章DP → 第8章回溯 → 第4章DFS/BFS → 第3章伸展树。

---

一、第2章：复杂度、渐近记号、递推关系 ⭐⭐⭐⭐⭐

1. 时间复杂度到底在分析什么？⭐⭐⭐⭐⭐

时间复杂度不是在问“程序运行几秒”，而是在问：

当输入规模 $n$ 变大时，算法运行时间按什么速度增长。

例如：

for (int i = 0; i < n; i++) {
    cout << i;
}

循环执行 $n$ 次，所以时间复杂度是：

$$O(n)$$

再看双重循环：

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        cout << i << j;
    }
}

外层执行 $n$ 次，每次内层执行 $n$ 次，总共 $n^2$ 次，所以：

$$O(n^2)$$

如果内层不是从 $0$ 到 $n$，而是从 $i$ 到 $n$：

for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
        cout << i << j;
    }
}

执行次数为：

$$(n)+(n-1)+(n-2)+\cdots+1=\frac{n(n+1)}2$$

去掉常数和低阶项后仍是：

$$O(n^2)$$

考试易错点：
不要看到两层循环就机械写 $O(n^2)$，要看每层循环次数是否和 $n$ 有关。例如：

for (int i = 0; i < n; i++) {
    for (int j = 0; j < 100; j++) {
        cout << i << j;
    }
}

总次数为 $100n$，所以复杂度是：

$$O(n)$$

不是 $O(n^2)$。

---

2. 最好、最坏、平均复杂度怎么区分？⭐⭐⭐⭐

以顺序查找为例，在数组中查找关键字 $x$：

for (int i = 0; i < n; i++) {
    if (a[i] == x) return i;
}
return -1;

情况	发生场景	比较次数	复杂度
最好情况	第一个元素就是 $x$	1	$O(1)$
最坏情况	最后一个元素才是 $x$，或不存在	$n$	$O(n)$
平均情况	$x$ 等概率出现在任意位置	$(n+1)/2$	$O(n)$

考试默认通常问的是最坏情况复杂度，因为最坏情况能给算法性能提供保证。

---

3. 渐近记号：大O、大Ω、大Θ怎么写证明？⭐⭐⭐⭐⭐

（1）大O：证明“不会超过”

要证明：

$$f(n)=O(g(n))$$

就是要找两个常数 $c>0,n_0>0$，使得：

$$f(n)\le cg(n),\quad n\ge n_0$$

例：证明

$$3n^2+2n+1=O(n^2)$$

当 $n\ge1$ 时：

$$2n\le2n^2,\quad 1\le n^2$$

所以：

$$3n^2+2n+1\le3n^2+2n^2+n^2=6n^2$$

取：

$$c=6,\quad n_0=1$$

故：

$$3n^2+2n+1=O(n^2)$$

答题模板：

当 n ≥ n0 时，有低阶项 ≤ 若干倍最高阶项，
因此 f(n) ≤ c·g(n)。
取 c=..., n0=...，
所以 f(n)=O(g(n))。

（2）大Ω：证明“至少这么快”

要证明：

$$f(n)=\Omega(g(n))$$

就是找 $c,n_0$，使得：

$$f(n)\ge cg(n),\quad n\ge n_0$$

例：

$$3n^2+2n+1=\Omega(n^2)$$

因为：

$$3n^2+2n+1\ge3n^2$$

取 $c=3,n_0=1$ 即可。

（3）大Θ：证明“同阶”

要证明：

$$f(n)=\Theta(g(n))$$

需要同时证明：

$$f(n)=O(g(n))$$

和：

$$f(n)=\Omega(g(n))$$

例：

$$3n^2+2n+1=\Theta(n^2)$$

上面已证：

$$3n^2+2n+1\le6n^2$$

又因为：

$$3n^2+2n+1\ge3n^2$$

因此：

$$3n^2\le3n^2+2n+1\le6n^2$$

所以：

$$3n^2+2n+1=\Theta(n^2)$$

考试最常见错误：
写“大O就是最坏情况，大Ω就是最好情况”。这不严谨。大O/Ω/Θ本质是函数增长上界/下界/紧界，不直接等于最好/最坏情况。

---

4. 递推关系怎么解？⭐⭐⭐⭐⭐

递归算法常常得到递推式。考试经常要求你从递推式推出复杂度。

方法1：展开法

例：

$$T(n)=T(n-1)+2,\quad T(0)=2$$

展开：

$$T(n)=T(n-1)+2$$ $$=T(n-2)+2+2$$ $$=T(n-3)+2+2+2$$ $$=\cdots$$ $$=T(0)+2n$$

所以：

$$T(n)=2+2n=\Theta(n)$$

方法2：递归树法

例：

$$T(n)=2T(n/2)+n$$

画递归树：

层数	子问题数	每个子问题规模	每层总代价
0	1	$n$	$n$
1	2	$n/2$	$n$
2	4	$n/4$	$n$
…	…	…	…
$\log n$	$n$	1	$n$

共有 $\log n+1$ 层，每层代价 $n$，所以：

$$T(n)=\Theta(n\log n)$$

方法3：主方法

遇到：

$$T(n)=aT(n/b)+f(n)$$

先算：

$$n^{\log_b a}$$

然后比较 $f(n)$ 与 $n^{\log_b a}$。

例1：

$$T(n)=4T(n/2)+n$$

有：

$$a=4,\quad b=2,\quad n^{\log_b a}=n^{\log_2 4}=n^2$$

而：

$$f(n)=n$$

比 $n^2$ 小，所以：

$$T(n)=\Theta(n^2)$$

例2：

$$T(n)=2T(n/2)+n$$

有：

$$n^{\log_2 2}=n$$

$f(n)=n$ 与它同阶，所以：

$$T(n)=\Theta(n\log n)$$

例3：

$$T(n)=2T(n/2)+n^2$$

有：

$$n^{\log_2 2}=n$$

$f(n)=n^2$ 更大，所以：

$$T(n)=\Theta(n^2)$$

主方法答题模板：

该递推式中 a=..., b=..., f(n)=...
n^{log_b a}=...
比较 f(n) 与 n^{log_b a}：
属于主方法第 ... 种情况，
所以 T(n)=...

---

二、第3章：伸展树重难点详解 ⭐⭐⭐⭐

1. 为什么伸展树不用严格平衡也能快？⭐⭐⭐⭐

普通二叉搜索树的问题是：
如果插入序列是有序的，例如：

$$1,2,3,4,5,6$$

树可能退化成链表，查找最坏需要 $O(n)$。

AVL树、红黑树的做法是：
每次插入删除后维护严格或近似平衡。

伸展树的做法不同：

它不维护显式平衡，而是把“刚访问过的结点”旋转到根。

这样做基于一个经验规律：
刚刚访问过的元素，很可能近期还会再次访问。把它放到根附近，可以降低后续访问代价。

所以伸展树的单次操作最坏可能是 $O(n)$，但连续多次操作的平均分摊代价是：

$$O(\log n)$$

考试答题时要强调：

伸展树不是严格平衡树，而是自调节搜索树。
它通过访问后伸展，把近期访问的结点移到根。
因此单次操作最坏可能 O(n)，但分摊代价 O(log n)。

---

2. 伸展操作到底怎么判断？⭐⭐⭐⭐

设当前伸展结点为 $x$，父结点为 $p$，祖父结点为 $g$。

情况1：父结点就是根

只做一次单旋。

$x$ 位置	操作
$x$ 是 $p$ 左孩子	zig，右旋
$x$ 是 $p$ 右孩子	zag，左旋

情况2：$x,p,g$ 同向

若 $x$ 是 $p$ 的左孩子，$p$ 是 $g$ 的左孩子：

    g
   /
  p
 /
x

这是 zig-zig。操作顺序：

1. 先对 $g$ 右旋；
2. 再对 $p$ 右旋。

若 $x$ 是 $p$ 的右孩子，$p$ 是 $g$ 的右孩子，就是 zag-zag，对称地做两次左旋。

情况3：$x,p,g$ 反向

若 $x$ 是 $p$ 的右孩子，$p$ 是 $g$ 的左孩子：

  g
 /
p
 \
  x

这是 zig-zag。操作顺序：

1. 先对 $p$ 左旋；
2. 再对 $g$ 右旋。

若 $x$ 是 $p$ 的左孩子，$p$ 是 $g$ 的右孩子，就是 zag-zig，对称处理。

记忆方法：

同向：先转祖父，再转父亲。
异向：先转父亲，再转祖父。

---

三、第4章：BFS、DFS、关节点 ⭐⭐⭐⭐⭐

1. BFS为什么能求无权图最短路径？⭐⭐⭐⭐⭐

BFS是“按层扩展”的：

• 第0层：源点 $s$；
• 第1层：距离 $s$ 为1条边的结点；
• 第2层：距离 $s$ 为2条边的结点；
• 第3层：距离 $s$ 为3条边的结点。

由于队列先进先出，BFS一定先处理距离小的结点，再处理距离大的结点。

因此，当某个结点第一次被BFS发现时，得到的路径一定是从源点到该结点的最短边数路径。

标准证明思路：

BFS从源点开始逐层访问。
队列保证所有距离为 k 的结点会在距离 k+1 的结点之前出队。
所以某结点第一次被发现时，其路径长度最短。

注意：
BFS只能直接求无权图最短路径。
如果图有权值，不能简单用BFS，应该用Dijkstra、Bellman-Ford或Floyd等算法。

---

2. DFS时间戳怎么理解？⭐⭐⭐⭐⭐

DFS给每个结点两个时间：

• $d[u]$：第一次发现 $u$ 的时间；
• $f[u]$：从 $u$ 出发的所有边都处理完的时间。

因为DFS会“一条路走到底”，所以一个结点的所有后代都会在它完成之前完成。

若 $v$ 是 $u$ 的后代，则一定有：

$$d[u]<d[v]<f[v]<f[u]$$

这就是括号定理。

可以理解成：

u 被打开左括号：d[u]
  v 被打开左括号：d[v]
  v 被关闭右括号：f[v]
u 被关闭右括号：f[u]

所以区间 $[d[v],f[v]]$ 完全包含在 $[d[u],f[u]]$ 中。

考试会怎么出：

给你几个点的 $d,f$ 值，判断祖先/后裔关系。

例：

$$d[u]=1,f[u]=10,d[v]=3,f[v]=6$$

因为：

$$1<3<6<10$$

所以 $v$ 是 $u$ 的后裔。

---

3. DFS边分类怎么判断？⭐⭐⭐⭐

在有向图DFS中，边可以分成四类：

边	判断方法	含义
树边	访问白色结点	DFS真正走过的边
反向边	指向灰色祖先	表示存在环
正向边	指向黑色后裔	祖先到后裔的非树边
交叉边	指向其他黑色结点	不属于祖先后裔关系

最重要结论：

$$有向图无环 \iff DFS中没有反向边$$

为什么？
反向边是从某个结点指回它的祖先，祖先到该结点已有一条DFS树路径，再加上这条反向边就构成环。

答题模板：

若DFS中存在反向边 (u,v)，则v是u的祖先。
DFS树中从v到u存在路径，再加上边(u,v)，构成有向环。
因此有反向边说明有环。
反过来，若有环，DFS遍历该环时必会产生一条指向灰色祖先的反向边。

---

4. 关节点和Low值为什么这么判？⭐⭐⭐⭐

（1）根结点

DFS树的根如果有两个或更多孩子，则它是关节点。

原因：
根的不同孩子子树之间不能通过非树边互相连接，否则它们会在DFS中属于同一个子树。删除根后，这些子树分离。

所以：

根结点是关节点 ⇔ 根在DFS树中至少有两个孩子。

（2）非根结点

对非根结点 $u$，若存在孩子 $w$ 满足：

$$Low[w]\ge d[u]$$

则 $u$ 是关节点。

这里 $Low[w]$ 表示：
从 $w$ 的子树出发，最多经过一条反向边，能到达的最早祖先的发现时间。

若：

$$Low[w]<d[u]$$

说明 $w$ 的子树能绕过 $u$ 回到 $u$ 的祖先，删除 $u$ 后仍可连通到上面。

若：

$$Low[w]\ge d[u]$$

说明 $w$ 子树无法绕过 $u$ 到达 $u$ 的祖先。删除 $u$ 后，$w$ 子树断开，所以 $u$ 是关节点。

答题模板：

Low[w] 表示 w 子树能通过反向边到达的最早祖先。
如果 Low[w] ≥ d[u]，说明 w 子树无法通过反向边到达 u 的祖先。
删除 u 后，w 子树与图其余部分断开。
因此 u 是关节点。

---

四、第5章：分治法核心算法详解 ⭐⭐⭐⭐⭐

1. 分治法为什么通常得到递归？⭐⭐⭐⭐⭐

分治法三步：

1. 分解 Divide；
2. 求解 Conquer；
3. 合并 Combine。

因为子问题与原问题类型相同，只是规模变小，所以最自然的写法就是递归。

例如归并排序：

要排序 A[0..n-1]
= 排序左半部分 + 排序右半部分 + 合并两个有序表

这显然又调用“排序”自身，所以是递归。

---

2. 分治和动态规划怎么区分？⭐⭐⭐⭐⭐

这类题非常容易考简答。

对比点	分治	动态规划
子问题	相互独立	大量重叠
求解方式	递归求解后合并	保存子问题结果
是否重复计算	一般无严重重复	若不用表会大量重复
典型例子	归并排序、快速排序	LCS、矩阵连乘、0/1背包

例：归并排序中，左半部分和右半部分互不重叠，所以适合分治。

例：斐波那契递归中，$F(n-1)$ 和 $F(n-2)$ 都会反复用到 $F(n-3),F(n-4)$ 等子问题，所以适合DP。

标准答案：

分治法要求子问题相互独立，递归求解后合并；
动态规划适用于子问题重叠的情形，通过保存子问题结果避免重复计算。

---

3. 二分搜索为什么是 $O(\log n)$？⭐⭐⭐⭐⭐

二分搜索每次比较后，问题规模减半：

$$n\to n/2\to n/4\to n/8\to\cdots\to1$$

设经过 $k$ 次后规模变为1：

$$\frac{n}{2^k}=1$$

所以：

$$2^k=n$$ $$k=\log_2 n$$

因此二分搜索复杂度为：

$$O(\log n)$$

考试细节：

二分搜索必须满足前提：表有序。
若数据无序，不能直接二分。

---

4. 归并排序为什么稳定且一定 $O(n\log n)$？⭐⭐⭐⭐⭐

归并排序每次一分为二，递归深度为：

$$\log n$$

每一层都要把所有元素合并一次，总合并代价是：

$$O(n)$$

所以：

$$O(n\log n)$$

它与数据初始顺序无关，无论最好、平均、最坏都是：

$$\Theta(n\log n)$$

稳定性来自合并时的规则：

当左右两个元素相等时，先取左边元素。

这样原来在前面的相等元素仍在前面。

---

5. 快速排序为什么平均快但最坏慢？⭐⭐⭐⭐⭐

快速排序的关键是分划 pivot。

最好情况

每次pivot都把序列均分：

$$T(n)=2T(n/2)+O(n)$$

所以：

$$T(n)=O(n\log n)$$

最坏情况

每次pivot都是最小或最大，分成：

$$0 \text{ 和 } n-1$$

于是：

$$T(n)=T(n-1)+O(n)$$

展开：

$$T(n)=n+(n-1)+(n-2)+\cdots+1=O(n^2)$$

为什么平均情况仍好？

随机情况下，pivot不太可能每次都极端不平衡。平均递归树高度约为 $O(\log n)$，每层分划代价为 $O(n)$，所以平均：

$$O(n\log n)$$

常考对比：

排序	最坏	平均	稳定性	额外空间
归并排序	$O(n\log n)$	$O(n\log n)$	稳定	$O(n)$
快速排序	$O(n^2)$	$O(n\log n)$	不稳定	平均 $O(\log n)$ 递归栈

---

6. 选择问题为什么可以做到线性时间？⭐⭐⭐⭐

选择问题是找第 $k$ 小元素，不需要把所有元素完全排序。

如果先排序，再取第 $k$ 个：

$$O(n\log n)$$

但选择问题只需要定位一个元素，可以更快。

基于Partition的选择：

分划后，pivot位置已经确定。
如果pivot正好是第k小，结束；
如果第k小在左边，只递归左边；
如果第k小在右边，只递归右边。

平均情况下每次只处理一边，所以平均：

$$O(n)$$

但如果每次pivot极差，最坏：

$$O(n^2)$$

线性选择算法通过“中位数的中位数”选择较好pivot，保证每次能丢掉固定比例的元素，所以最坏也能达到：

$$O(n)$$

---

五、第6章：贪心法核心算法详解 ⭐⭐⭐⭐⭐

1. 贪心法最关键的不是算法，而是证明 ⭐⭐⭐⭐⭐

很多同学觉得贪心法简单，因为“每次选最大的/最小的”。
但考试重点恰恰是：

你凭什么这样选一定最优？

所以贪心题必须写证明。

贪心正确性一般证明两个性质：

（1）贪心选择性质

存在一个最优解，它包含当前的贪心选择。

这通常用交换论证证明：

设O是一个最优解。
如果O已经包含贪心选择，则无需处理。
如果O不包含贪心选择，就把O中的某个选择替换为贪心选择。
证明替换后仍可行，且目标函数不变差。
所以存在一个包含贪心选择的最优解。

（2）最优子结构

做出贪心选择后，剩下的问题仍是同类型的子问题，其最优解与当前选择组合后构成原问题最优解。

考试答题必须写：

该问题具有贪心选择性质和最优子结构，因此贪心算法正确。

不能只写“每次选最优，所以全局最优”。

---

2. 一般背包为什么能贪心？⭐⭐⭐⭐⭐

一般背包允许物品分割：

$$0\le x_i\le1$$

所以只要某物品单位价值高，就应该尽可能多装。

贪心准则：

$$\frac{p_i}{w_i}\text{ 从大到小排序}$$

为什么正确？

假设有两个物品 $i,j$，并且：

$$\frac{p_i}{w_i}>\frac{p_j}{w_j}$$

如果一个方案中还有 $j$ 被装入，而 $i$ 没有尽量装满，那么可以从 $j$ 中拿出一小部分重量 $\Delta$，换成同样重量的 $i$。

收益变化：

$$\Delta\cdot \frac{p_i}{w_i}-\Delta\cdot \frac{p_j}{w_j}>0$$

收益变大，原方案不可能最优。
所以最优方案一定优先装单位价值高的物品。

例题详解

背包容量 $M=20$，物品：

物品	重量	收益	单位收益
0	18	25	1.39
1	15	24	1.60
2	10	15	1.50

排序：物品1 → 物品2 → 物品0。

装入：

1. 装物品1，重量15，收益24，剩余容量5；
2. 物品2只能装 $5/10=0.5$，收益 $15\times0.5=7.5$。

总收益：

$$24+7.5=31.5$$

解向量按原编号：

$$x_0=0,\quad x_1=1,\quad x_2=0.5$$

---

3. 0/1背包为什么不能用同样贪心？⭐⭐⭐⭐⭐

0/1背包中：

$$x_i\in\{0,1\}$$

物品不能切开。

反例：

背包容量 $M=50$：

物品	重量	价值	单位价值
1	10	60	6
2	20	100	5
3	30	120	4

按单位价值贪心：

• 选1，剩余40；
• 选2，剩余20；
• 不能选3；
• 总价值160。

但最优解是选2和3：

$$100+120=220$$

所以0/1背包不能保证用单位价值贪心得到最优解。

考试回答：

一般背包允许分割，单位价值高的物品可以部分装入，所以贪心正确。
0/1背包不允许分割，局部最优选择可能造成容量浪费，因此不能保证全局最优。

---

4. 带时限作业排序怎么做？⭐⭐⭐⭐

题型常给作业收益 $p_i$ 和期限 $d_i$，每个作业耗时1。
目标：在截止期限内完成尽可能高收益的作业集合。

贪心准则：

按收益从大到小考虑作业。
每个作业尽量安排在不超过其截止期限的最晚空闲时间片。

为什么安排在最晚？
因为越早的时间片越宝贵，可能留给截止期限更早的作业。把当前作业放到尽可能晚的位置，可以保留更多灵活性。

例：

作业	收益	截止期
A	100	2
B	19	1
C	27	2
D	25	1
E	15	3

按收益排序：A、C、D、B、E。

最大期限为3，有时间片1、2、3。

• A截止2，放最晚空位2；
• C截止2，时间片2已占，放时间片1；
• D截止1，时间片1已占，不能放；
• B截止1，不能放；
• E截止3，放时间片3。

选择：C、A、E，总收益：

$$27+100+15=142$$

---

5. 最佳合并模式为什么每次合并最小两个？⭐⭐⭐⭐

合并文件时，某个文件如果早早被合并，它的长度会在后续合并中反复参与代价。
所以长度小的文件应该放在更深的位置，长度大的文件放在更浅的位置。

这与哈夫曼树完全一致：

• 文件长度是权值；
• 合并过程是构造哈夫曼树；
• 总合并代价是带权外路径长度。

每次选两个最小的合并，能保证总带权路径长度最小。

答题关键词：

最佳合并模式等价于哈夫曼树构造。
每次选择两个权值最小的文件合并，可得到最小带权外路径长度。

---

6. Prim和Kruskal怎么区分？⭐⭐⭐⭐⭐

两者都求最小生成树，但思路不同。

Prim：扩展一棵树

从一个起点开始，每次选一条连接：

$$S \text{ 与 } V-S$$

的最小边。

关键词：

扩点、维护一个已选顶点集合、适合稠密图。

Kruskal：从小边开始选

先把所有边按权值排序，每次选最小的边，只要不成环就加入。

关键词：

选边、排序、并查集判环、适合稀疏图。

对比表

项目	Prim	Kruskal
每步选择	连通树内外的最小边	全图当前最小且不成环的边
维护对象	顶点集合	边集合
常用结构	lowcost数组	并查集
复杂度	邻接矩阵 $O(n^2)$	$O(e\log e)$
适合	稠密图	稀疏图

---

7. Dijkstra为什么是贪心算法？⭐⭐⭐⭐⭐

Dijkstra每一步选择：

当前还未确定最短路的结点中，$d$ 值最小的结点。

这就是贪心选择。

为什么这个选择正确？
因为所有边权非负。设当前选中结点 $u$，它的 $d[u]$ 最小。
若存在一条经过其他未选结点再到 $u$ 的更短路径，那么这条路径必须先到某个未选结点 $v$。由于边权非负，从源点到 $v$ 的距离不会小于当前 $d[v]$，而 $d[v]\ge d[u]$，所以不可能再得到比 $d[u]$ 更短的路径。

所以 $u$ 的最短距离可以被最终确定。

Dijkstra手算步骤

1. 初始化：
   • 源点 $d=0$；
   • 其他点 $d=\infty$；
   • $S=\emptyset$。
2. 选 $V-S$ 中 $d$ 最小的点 $u$ 加入 $S$。
3. 用 $u$ 松弛所有邻边：

$$d[v]=\min(d[v],d[u]+w(u,v))$$

1. 重复直到所有点确定。

考试易错点：

• 不要忘记更新前驱 path[v]；
• Dijkstra不能用于有负权边的图；
• 邻接矩阵版本复杂度通常写 $O(n^2)$。

---

六、第7章：动态规划核心算法详解 ⭐⭐⭐⭐⭐

1. DP题目应该怎么想？⭐⭐⭐⭐⭐

DP最重要的是把问题变成表格。

答题时必须写清楚：

① 状态定义：dp[i][j]表示什么；
② 边界条件：最小子问题怎么取值；
③ 状态转移：大问题如何由小问题得到；
④ 填表顺序：为什么转移时需要的值已经算好；
⑤ 构造最优解：如果题目要求路径/方案，需要记录决策；
⑥ 复杂度分析。

很多同学丢分是因为只写公式，不解释状态含义。
状态含义没写清楚，公式即使对了也可能被扣分。

---

2. 最优子结构怎么证明？⭐⭐⭐⭐⭐

以矩阵连乘为例。
如果 $A_i\cdots A_j$ 的最优加括号方式最后在 $k$ 处分开：

$$(A_i\cdots A_k)(A_{k+1}\cdots A_j)$$

那么左半部分 $A_i\cdots A_k$ 必须也是最优加括号。

反证：
如果左半部分不是最优，则存在另一种左半部分加括号方式乘法次数更少。用它替换原方案左半部分，就得到一个更优的整体方案，与“原整体最优”矛盾。

这就是DP最常用证明套路：

假设整体最优解中包含的某个子问题解不是最优的。
则可用该子问题的更优解替换它，
得到更优整体解，矛盾。
所以整体最优解包含子问题最优解。

---

3. 矩阵连乘为什么要枚举最后断点？⭐⭐⭐⭐⭐

矩阵乘法满足结合律：

$$A_1A_2A_3A_4$$

可以有多种加括号方式：

$$(A_1A_2)(A_3A_4)$$ $$A_1((A_2A_3)A_4)$$ $$((A_1A_2)A_3)A_4$$

DP的关键是看“最后一次乘法”。
最后一次乘法一定把矩阵链分成左右两段：

$$(A_i\cdots A_k)(A_{k+1}\cdots A_j)$$

其中 $k$ 可以从 $i$ 到 $j-1$。

所以递推为：

$$m[i][j]=\min_{i\le k<j}\{m[i][k]+m[k+1][j]+p_ip_{k+1}p_{j+1}\}$$

其中：

• $m[i][k]$：左半段最优代价；
• $m[k+1][j]$：右半段最优代价；
• $pip{k+1}p_{j+1}$：最后两矩阵相乘代价。

填表顺序：

先算长度为1的链：

$$m[i][i]=0$$

再算长度为2、3、4……直到整个链。

因为 $m[i][j]$ 依赖更短区间，所以必须按链长递增填表。

---

4. LCS为什么有三种情况？⭐⭐⭐⭐⭐

设：

$$X=x_1x_2\cdots x_m$$ $$Y=y_1y_2\cdots y_n$$

状态：

$$c[i][j]=X[1..i]\text{ 与 }Y[1..j]\text{ 的LCS长度}$$

情况1：最后字符相等

若：

$$x_i=y_j$$

则这个字符可以放入LCS末尾：

$$c[i][j]=c[i-1][j-1]+1$$

情况2：最后字符不相等

若：

$$x_i\ne y_j$$

那么LCS不可能同时以这两个字符结尾。
只能考虑：

• 不用 $x_i$：$c[i-1][j]$；
• 不用 $y_j$：$c[i][j-1]$。

所以：

$$c[i][j]=\max(c[i-1][j],c[i][j-1])$$

恢复LCS的方法：

从 $c[m][n]$ 往回走：

• 若 $x_i=y_j$：输出该字符，走左上；
• 否则走值较大的方向；
• 若上和左相等，任选一个，可能得到不同LCS。

---

5. 0/1背包DP为什么是“选或不选”？⭐⭐⭐⭐⭐

对第 $i$ 件物品，只有两种选择：

1. 不选它；
2. 选它。

状态：

$$f[i][j]=前i件物品在容量j下可获得的最大收益$$

不选第 $i$ 件

收益就是：

$$f[i-1][j]$$

选第 $i$ 件

前提是：

$$j\ge w_i$$

选了它之后，剩余容量为：

$$j-w_i$$

收益为：

$$f[i-1][j-w_i]+p_i$$

所以：

$$f[i][j]=\max\{f[i-1][j],f[i-1][j-w_i]+p_i\}$$

如果 $j<w_i$，装不下，只能不选：

$$f[i][j]=f[i-1][j]$$

和一般背包区别：

问题	$x_i$	常用方法
一般背包	$0\le x_i\le1$	贪心
0/1背包	$x_i\in{0,1}$	动态规划/回溯/分枝限界

---

七、第8章：回溯法核心算法详解 ⭐⭐⭐⭐⭐

1. 回溯法本质是什么？⭐⭐⭐⭐⭐

回溯法就是：

深度优先搜索状态空间树，发现不可能成功就退回上一层。

它不是简单暴力，因为它有剪枝。

回溯法过程：

先做一个选择；
如果这个选择仍可能得到答案，就继续往下搜索；
如果这个选择已经不可能得到答案，就撤销选择，换下一个选择。

这就是“试探—失败—退回—再试探”。

---

2. 显式约束和隐式约束怎么区分？⭐⭐⭐⭐⭐

以n皇后为例。

解向量：

$$X=(x_0,x_1,\dots,x_{n-1})$$

其中 $x_i$ 表示第 $i$ 行皇后放在哪一列。

显式约束：

$$x_i\in\{0,1,\dots,n-1\}$$

即每个皇后只能放在棋盘列范围内。

隐式约束：

• 任意两个皇后不同列；
• 任意两个皇后不同斜线。

也就是：

$$x_i\ne x_j$$

且：

$$|x_i-x_j|\ne |i-j|$$

区别一句话：

显式约束定义候选解空间；
隐式约束从候选解中筛出可行解。

---

3. n皇后Place函数为什么这样写？⭐⭐⭐⭐⭐

假设已经放好第 $0$ 到 $k-1$ 行，现在尝试第 $k$ 行放在 $x[k]$ 列。

只需要检查之前的皇后：

for (int i = 0; i < k; i++) {
    if (x[i] == x[k]) return false;
    if (abs(x[i]-x[k]) == abs(i-k)) return false;
}
return true;

为什么？

• 同一行不用检查，因为每一层只放一行；
• 同列冲突：$x[i]=x[k]$；
• 同斜线冲突：行差等于列差：

$$|i-k|=|x[i]-x[k]|$$

考试写n皇后回溯时，必须写出这个判定条件。

---

4. 子集和数怎么剪枝？⭐⭐⭐⭐

问题：给定正数集合，找和为 $M$ 的子集。

假设：

• 当前和为 $s$；
• 剩余元素总和为 $r$；
• 下一个元素为 $w_k$。

可以剪枝的情况：

情况1：当前和已经超过目标

$$s>M$$

由于所有数都是正数，继续加只会更大，所以剪枝。

情况2：即使全选也达不到目标

$$s+r<M$$

说明后面所有元素都选上也不够，剪枝。

情况3：选择下一个元素会超过目标

$$s+w_k>M$$

则“选 $w_k$”这条分支不可走。

这类题答题要写清楚：

因为所有元素为正数，所以当前和超过M后不可能再减少；
若当前和加剩余总和仍小于M，则不可能达到M。

---

5. 图m着色为什么是 $m^n$ 规模？⭐⭐⭐⭐

有 $n$ 个结点，每个结点有 $m$ 种颜色。
如果不剪枝，候选着色方案数是：

$$m\times m\times\cdots\times m=m^n$$

隐式约束是：
任意相邻结点颜色不同。

在第 $k$ 个结点选颜色时，只需检查它与已经染色的邻接点是否冲突：

bool Ok(int k) {
    for (int j = 0; j < n; j++) {
        if (graph[k][j] && x[k] == x[j])
            return false;
    }
    return true;
}

若冲突，剪去该颜色分支。

---

6. 0/1背包回溯为什么要用限界函数？⭐⭐⭐⭐

0/1背包是最优化问题。
如果只是用约束函数，只能剪去超重分支，仍可能搜索大量不可能超过当前最优解的分支。

限界函数用于估计：

从当前结点继续往下，理论上最多还能获得多少收益。

若这个上界都不超过当前最优值，就没必要搜索。

常用上界：
用“一般背包贪心”估计剩余物品最大可能收益。因为允许分割会比0/1情况更乐观，所以这是一个合法上界。

若：

$$bound\le best$$

则剪枝。

答题模板：

先按单位价值从大到小排序。
对当前结点，用可分割背包方法估计剩余容量下的最大可能收益bound。
若bound不超过当前最优值best，则该子树不可能产生更优解，剪枝。

---

4–5星题型标准答题模板汇总 ⭐⭐⭐⭐⭐

1. 复杂度分析题模板

设输入规模为 n。
首先统计基本操作执行次数/写出递推式。
若为循环，计算循环总次数；
若为递归，建立 T(n)=...。
然后解得 T(n)=...。
忽略常数因子和低阶项，所以时间复杂度为 O/Θ(...)。
空间复杂度主要考虑数组/递归栈/辅助表，因此为 ...。

2. 分治算法设计题模板

Divide：将规模为 n 的问题分成若干个同类型子问题；
Conquer：递归求解这些子问题；
Combine：将子问题解合并为原问题解；
递归出口：当规模足够小时直接求解；
递推式：T(n)=...
解得复杂度：...

3. 贪心算法设计题模板

贪心准则：每一步选择 ...
可行性判定：加入该选择后检查 ...
算法步骤：排序/选择/检查/加入解集。
正确性证明：
① 贪心选择性质：通过交换论证证明存在包含当前贪心选择的最优解；
② 最优子结构：做出贪心选择后，剩余部分仍是同类型子问题；
因此算法正确。
复杂度：主要由排序/选择/数据结构决定，为 ...

4. 动态规划算法设计题模板

状态定义：dp[i][j] 表示 ...
边界条件：dp[...]=...
状态转移：
若 ...，dp[i][j]=...
否则 dp[i][j]=...
填表顺序：由于 dp[i][j] 依赖 ...，所以按 ... 顺序计算。
构造解：用 path/s/b 数组记录决策，从最终状态回溯。
复杂度：状态数 × 每个状态转移代价 = ...

5. 回溯算法设计题模板

解向量：X=(x1,x2,...,xn)，其中 xi 表示 ...
显式约束：xi ∈ ...
隐式约束：...
状态空间树：排列树/子集树/m叉树。
搜索策略：深度优先搜索。
剪枝函数：
① 约束函数用于排除不可行解；
② 限界函数用于排除不可能产生最优解的子树。
复杂度：最坏情况下为 ...，剪枝可减少实际搜索量。

---

第2章 算法分析基础 ⭐⭐⭐⭐⭐

2.1 好算法与复杂度基础 ⭐⭐⭐⭐

一个好的算法通常具有四个重要特性：

特性	含义	考试提醒
正确性	算法结果满足题目要求	证明算法必须先说明正确性
简明性	思路清晰，易理解和实现	伪代码要层次清楚
效率	时间与空间使用合理	复杂度分析是必考点
最优性	达到该类问题所需时间下界	常与“排序下界”“搜索下界”结合考

程序健壮性：输入不合法时程序能做适当处理，不造成严重后果。
PPT说明：本课程默认算法输入合法，通常不重点讨论输入检测。

影响程序运行时间的因素：

1. 程序所依赖的算法；
2. 问题规模和输入数据；
3. 计算机系统性能。

---

2.2 时间复杂度与空间复杂度 ⭐⭐⭐⭐⭐

1. 时间复杂度

设算法 $A$ 在输入 $I$ 上运行，问题规模为 $n$，则运行时间可记作：

$$T(n,I)$$

常见分析角度：

类型	含义
最好时间复杂度	对规模为 $n$ 的所有输入，运行时间最小
最坏时间复杂度	对规模为 $n$ 的所有输入，运行时间最大
平均时间复杂度	对规模为 $n$ 的输入按概率求期望

考试默认：若题目未特别说明，一般分析最坏情况时间复杂度。

2. 程序步

程序步是语法或语义上有意义、且执行时间与问题规模无关的程序段。
引入程序步是为了简化算法的事前分析。

PPT例子：

float Sum(float list[], const int n) {
    float tempsum = 0.0;
    for (int i = 0; i < n; i++)
        tempsum += list[i];
    return tempsum;
}

程序步计数结果：

$$T(n)=2n+3=\Theta(n)$$

递归求和：

float RSum(float list[], const int n) {
    if (n)
        return RSum(list, n-1) + list[n-1];
    return 0;
}

递推式：

$$T(n)=2+T(n-1),\quad T(0)=2$$

解得：

$$T(n)=2n+2=\Theta(n)$$

3. 空间复杂度

算法运行所需空间包括：

空间类型	含义
固定空间需求	与输入规模无关，如代码、常量、简单变量
可变空间需求	与输入规模相关，如数组、递归栈、动态分配空间

---

2.3 渐近表示法 ⭐⭐⭐⭐⭐

1. 大 O 记号：渐进上界

若存在正常数 $c,n_0$，使得当 $n\ge n_0$ 时：

$$f(n)\le c g(n)$$

则：

$$f(n)=O(g(n))$$

例：证明 $10n^2+4n+2=O(n^2)$。

当 $n\ge 5$ 时：

$$10n^2+4n+2\le 11n^2$$

取 $c=11,n_0=5$ 即可。

2. 大 $\Omega$ 记号：渐进下界

若存在正常数 $c,n_0$，使得当 $n\ge n_0$ 时：

$$f(n)\ge c g(n)$$

则：

$$f(n)=\Omega(g(n))$$

3. 大 $\Theta$ 记号：渐进紧确界

若存在正常数 $c_1,c_2,n_0$，使得当 $n\ge n_0$ 时：

$$c_1g(n)\le f(n)\le c_2g(n)$$

则：

$$f(n)=\Theta(g(n))$$

4. 小 o 记号：严格低阶

$$f(n)=o(g(n))$$

表示 $f(n)$ 比 $g(n)$ 增长严格慢。等价地：

$$\lim_{n\to\infty}\frac{f(n)}{g(n)}=0$$

5. 多项式定理

若：

$$f(n)=a_mn^m+a_{m-1}n^{m-1}+\cdots+a_1n+a_0,\quad a_m>0$$

则：

$$f(n)=\Theta(n^m)$$

也自然有：

$$f(n)=O(n^m),\quad f(n)=\Omega(n^m)$$

6. 常见复杂度大小顺序

多项式时间：

$$O(1)<O(\log n)<O(n)<O(n\log n)<O(n^2)<O(n^3)$$

指数级/超多项式：

$$O(2^n)<O(n!)<O(n^n)$$

易错点：$n!$ 的增长速度比 $2^n$ 快，但比 $n^n$ 慢。

---

2.4 递推关系与主方法 ⭐⭐⭐⭐⭐

1. 递推方程

递推方程使用一个或多个更小规模的函数值描述 $T(n)$，必须有初始条件。

常见解法：

方法	适合题型
替换法	先猜答案，再用归纳法证明
迭代法	不断展开递推式，化为求和
递归树法	分层统计每层代价
主方法	形如 $T(n)=aT(n/b)+f(n)$

2. 主方法

递推式：

$$T(n)=aT(n/b)+f(n)$$

其中 $a\ge1,b>1$。

令：

$$E=\log_b a$$

比较 $f(n)$ 与 $n^E$：

情况	条件	结论
情况1	$f(n)=O(n^{E-\varepsilon})$	$T(n)=\Theta(n^E)$
情况2	$f(n)=\Theta(n^E\log^k n)$	$T(n)=\Theta(n^E\log^{k+1}n)$
情况3	$f(n)=\Omega(n^{E+\varepsilon})$ 且满足正则条件	$T(n)=\Theta(f(n))$

正则条件通常写作：

$$a f(n/b)\le c f(n),\quad c<1$$

3. PPT典型例题

1. $T(n)=16T(n/4)+n$
   $a=16,b=4,E=\log_4 16=2$，$f(n)=n=O(n^{2-1})$。
   所以：

   $$T(n)=\Theta(n^2)$$

2. $T(n)=T(3n/7)+1$
   可看作 $a=1,b=7/3,E=0$，$f(n)=1=\Theta(n^0)$。
   所以：

   $$T(n)=\Theta(\log n)$$

3. $T(n)=3T(n/4)+n\log n$
   $E=\log_4 3<1$，$n\log n$ 更大，且满足正则条件。
   所以：

   $$T(n)=\Theta(n\log n)$$

4. $T(n)=2T(n/2)+n\log n$
   $E=1$，$f(n)=n\log n=\Theta(n^E\log n)$。
   所以：

   $$T(n)=\Theta(n\log^2 n)$$

---

第2章练习题与答案

练习2-1

判断：$3n^2+2n+1=\Theta(n^2)$。

答案：正确。因为当 $n\ge1$ 时：

$$3n^2\le 3n^2+2n+1\le 6n^2$$

取 $c_1=3,c_2=6,n_0=1$ 即可。

练习2-2

求递推式 $T(n)=T(n/2)+1$ 的复杂度。

答案：

每次规模减半，展开约 $\log_2 n$ 层，每层代价为 1。

$$T(n)=\Theta(\log n)$$

练习2-3

用主方法求 $T(n)=4T(n/2)+n$。

答案：

$a=4,b=2,E=\log_2 4=2$，$f(n)=n=O(n^{2-1})$，属于情况1。

$$T(n)=\Theta(n^2)$$

练习2-4

按增长速度从小到大排序：$n^2,\log n,n!,n\log n,2^n,n^3$。

答案：

$$\log n<n\log n<n^2<n^3<2^n<n!$$

练习2-5

递归算法的空间复杂度为什么通常要考虑递归栈？

答案：每次递归调用都会保存返回地址、局部变量和参数等信息。若递归深度为 $d$，每层额外空间为 $O(1)$，则递归栈空间为 $O(d)$。

---

第3章 伸展树与跳表 ⭐⭐⭐

3.1 字典与二叉搜索树 ⭐⭐⭐

字典是词条集合，词条包含关键字和其他信息。常见操作：

操作	含义
Search	按关键字查找元素
Insert	插入新元素，若关键字已存在则 Duplicate
Remove	删除指定关键字元素

字典可用线性表、散列表、搜索树、伸展树、跳表等结构表示。

二叉搜索树（BST）定义：

1. 根的左子树所有结点关键字小于根；
2. 根的右子树所有结点关键字大于根；
3. 左右子树也都是二叉搜索树。

BST的缺点：若插入序列有序，树会退化为链表，查找、插入、删除最坏为 $O(n)$。

---

3.2 伸展树 Splay Tree ⭐⭐⭐⭐

1. 基本思想

伸展树是一棵自调节二叉搜索树。每访问一个元素后，将该元素移动到根部，这个过程叫伸展。

目的：经常访问的元素靠近根，提高平均访问效率。

PPT结论：

在伸展树上执行 $m$ 次搜索、插入、删除，总时间为 $O(m\log n)$，平均分摊代价为 $O(\log n)$。

2. 哪个结点作为伸展结点？

操作	伸展结点
搜索成功	被找到的结点
插入成功	新插入的结点
删除成功	被删除结点的双亲
操作失败	搜索路径上遇到的最后一个结点

3. 旋转类型

情况	名称	含义
父结点是根，且当前结点是左孩子	zig	右旋
父结点是根，且当前结点是右孩子	zag	左旋
当前结点与父结点同为左孩子	zig-zig	先祖父右旋，再父右旋
当前结点与父结点同为右孩子	zag-zag	先祖父左旋，再父左旋
当前结点是右孩子，父结点是左孩子	zig-zag	先父左旋，再祖父右旋
当前结点是左孩子，父结点是右孩子	zag-zig	先父右旋，再祖父左旋

4. 旋转次数

若伸展结点到根路径长度为 $k$：

• $k$ 为偶数：执行 $k/2$ 次双重旋转；
• $k$ 为奇数：执行 $\lfloor k/2\rfloor$ 次双重旋转，再执行一次单旋。

---

3.3 跳表 Skip List ⭐⭐⭐

1. 为什么需要跳表？

有序数组可以二分搜索，但链表不能直接访问中间结点。
跳表在链表上增加多级索引，可替代平衡搜索树，获得良好的运算性能。

2. 跳表特征

1. 由若干层组成；
2. 第一层包含所有元素；
3. 每一层都是有序链表；
4. 若元素 $x$ 出现在第 $i$ 层，则所有比 $i$ 小的层都包含 $x$；
5. 第 $i$ 层元素通过 down 指针指向下一层相同值元素；
6. 每层通常包含 $-\infty,+\infty$ 哨兵；
7. top 指针指向最高层第一个元素。

3. 查找过程

从最高层开始：

p = top;
while (true) {
    while (p->next->key < x)
        p = p->next;
    if (p->down == NULL)
        return p->next;
    p = p->down;
}

查找策略：能向右就向右，不能向右就向下。

---

第3章练习题与答案

练习3-1

伸展树为什么属于自调节搜索树？

答案：因为它不显式维护平衡因子或颜色，而是在每次访问后通过旋转将访问结点移到根部，使近期频繁访问的结点更靠近根，从而获得较好的分摊性能。

练习3-2

搜索失败时，伸展树应伸展哪个结点？

答案：搜索过程中遇到的最后一个结点。

练习3-3

判断旋转类型：当前结点是父结点的左孩子，父结点也是祖父结点的左孩子。

答案：zig-zig，属于同向双旋。

练习3-4

跳表查找时为什么从最高层开始？

答案：最高层元素最少，能快速跳过大量不可能的元素；逐层下降后在底层定位，类似链表上的二分思想。

练习3-5

伸展树的单次操作最坏时间一定是 $O(\log n)$ 吗？

答案：不一定。单次操作最坏可能为 $O(n)$，但连续 $m$ 次操作的总时间为 $O(m\log n)$，即分摊 $O(\log n)$。

---

第4章 基本搜索和遍历方法 ⭐⭐⭐⭐

4.1 基本概念 ⭐⭐⭐

搜索分为：

类型	含义	代表算法
无知搜索	盲目、穷举，不利用启发信息	DFS、BFS、D-搜索
有知搜索	使用启发式信息	A* 等

图遍历常用颜色：

颜色	含义
White	未访问
Gray	已发现但未检测完成，活结点
Black	已检测完成，死结点

邻接表结构：

struct ENode {
    int adjVex;
    ENode* nextArc;
};
ENode** a;

---

4.2 BFS 广度优先搜索 ⭐⭐⭐⭐⭐

1. 基本思想

BFS从起点开始，先访问距离起点最近的结点，再逐层向外扩展。使用队列维护活结点。

BFS(u):
    color[u] = Gray
    enqueue(u)
    while queue not empty:
        u = dequeue()
        for each v adjacent to u:
            if color[v] == White:
                color[v] = Gray
                parent[v] = u
                enqueue(v)
        color[u] = Black

2. 考试重点

• BFS生成的是广度优先树/森林；
• 对无权图，BFS能求源点到其他结点的最短路径长度；
• 邻接表下时间复杂度为 $O(n+e)$；
• 空间复杂度通常为 $O(n)$。

---

4.3 DFS 深度优先搜索 ⭐⭐⭐⭐⭐

1. 基本思想

DFS从一个结点出发，沿一条路径尽可能深入，无法继续时回溯。常用递归或栈实现。

DFS(u):
    color[u] = Gray
    d[u] = time++
    for each v adjacent to u:
        if color[v] == White:
            parent[v] = u
            DFS(v)
    color[u] = Black
    f[u] = time++

其中：

• $d[u]$：发现时间；
• $f[u]$：完成时间。

2. 括号定理

对任意两个结点 $u,v$，区间 $[d[u],f[u]]$ 与 $[d[v],f[v]]$ 只有三种关系之一：

1. 完全分离：互不为后裔；
2. $[d[u],f[u]]$ 包含 $[d[v],f[v]]$：$v$ 是 $u$ 的后裔；
3. $[d[v],f[v]]$ 包含 $[d[u],f[u]]$：$u$ 是 $v$ 的后裔。

推论：

$$v\text{ 是 }u\text{ 的后裔}\iff d[u]<d[v]<f[v]<f[u]$$

3. 白色路径定理

在时刻 $d[u]$，若存在从 $u$ 到 $v$ 的路径，并且路径上除 $u$ 外均为白色，则 $v$ 是 DFS 森林中 $u$ 的后裔。

4. DFS边分类

边类型	说明
树边	DFS森林中的边，通常从灰到白
反向边	从后裔指向祖先，环也看作反向边
正向边	从祖先指向后裔的非树边
交叉边	其他边

重要性质：

1. 有向图无回路，当且仅当 DFS 中不包含反向边；
2. 无向图的 DFS 森林只包含树边和反向边。

---

4.4 双连通分量与关节点 ⭐⭐⭐⭐

1. 基本概念

概念	定义
关节点	删除该结点及相关边后，图分裂成两个或多个非空分图
双连通图	无向连通图不含关节点
双连通分量	最大双连通子图

等价关系：

无向连通图是双连通图 $\iff$ 任意两个结点之间存在简单回路 $\iff$ 图中不含关节点。

2. 关节点判定

对无向图做DFS，定义：

$$Low[u]=\min\{d[u],\min Low[w],\min d[x]\}$$

其中：

• $w$ 是 $u$ 的孩子；
• $(u,x)$ 是从 $u$ 出发的反向边。

判定规则：

结点类型	成为关节点的条件
根结点	至少有两个孩子
非根结点 $u$	存在孩子 $w$ 使得 $Low[w]\ge d[u]$

3. 双连通分量求法

DFS过程中把边压栈。
当访问到树边 $(u,v)$ 且满足：

$$Low[v]\ge d[u]$$

则从栈中弹出边，直到弹出 $(u,v)$，这些边组成一个新的双连通分量。

---

第4章练习题与答案

练习4-1

BFS和DFS分别使用什么数据结构维护活结点？

答案：BFS使用队列；DFS通常使用递归栈或显式栈。

练习4-2

若 $d[u]=2,f[u]=9,d[v]=4,f[v]=7$，则 $u,v$ 在DFS树中是什么关系？

答案：因为 $2<4<7<9$，所以 $v$ 是 $u$ 的后裔。

练习4-3

有向图中存在反向边说明什么？

答案：说明图中存在有向环。因此有向图无环当且仅当DFS中没有反向边。

练习4-4

根结点成为关节点的条件是什么？

答案：DFS树根至少有两个孩子。

练习4-5

非根结点 $u$ 有孩子 $w$，若 $Low[w]\ge d[u]$，为什么 $u$ 是关节点？

答案：说明以 $w$ 为根的子树不能通过反向边到达 $u$ 的祖先。删除 $u$ 后，该子树与图的其余部分断开，因此 $u$ 是关节点。

---

第5章 分治法 ⭐⭐⭐⭐⭐

5.1 分治法基本思想 ⭐⭐⭐⭐⭐

一个问题可用分治法求解，通常满足：

1. 能分解成若干个规模较小、相互独立、与原问题类型相同的子问题；
2. 子问题足够小时能直接求解；
3. 能将子问题的解组合成原问题的解。

通用模板：

Solution DandC(Problem P) {
    if (Small(P))
        return S(P);
    Divide(P, P1, P2, ..., Pk);
    return Combine(DandC(P1), DandC(P2), ..., DandC(Pk));
}

常见递推：

$$T(n)=aT(n/b)+cn^k$$

结论：

比较	复杂度
$a>b^k$	$\Theta(n^{\log_b a})$
$a=b^k$	$\Theta(n^k\log n)$
$a<b^k$	$\Theta(n^k)$

---

5.2 分治法求最大最小元 ⭐⭐⭐⭐

普通扫描同时求最大最小值：

$$2(n-1)$$

次比较。

分治法：

1. 若只有一个元素，最大值=最小值；
2. 若两个元素，只比较一次；
3. 否则左右递归求最大最小，再合并。

当 $n=2^k$ 时，比较次数：

$$\frac{3n}{2}-2$$

比普通方法少。

---

5.3 二分搜索 ⭐⭐⭐⭐⭐

问题：在有序表中查找元素 $x$。

递推式：

$$T(n)=T(n/2)+\Theta(1)$$

复杂度：

$$T(n)=\Theta(\log n)$$

二叉判定树性质：

1. 成功搜索比较次数不超过 $\lfloor\log n\rfloor+1$；
2. 不成功搜索需要 $\lfloor\log n\rfloor$ 或 $\lfloor\log n\rfloor+1$ 次比较；
3. 基于比较的搜索最坏至少需要 $\lfloor\log n\rfloor+1$ 次比较。

---

5.4 归并排序 ⭐⭐⭐⭐⭐

思想：

1. Divide：序列一分为二；
2. Conquer：递归排序左右子序列；
3. Combine：线性时间合并两个有序序列。

递推式：

$$T(n)=2T(n/2)+\Theta(n)$$

复杂度：

$$T(n)=\Theta(n\log n)$$

空间复杂度：

$$O(n)$$

---

5.5 快速排序 ⭐⭐⭐⭐⭐

1. 分划思想

选择主元 pivot，将序列分为：

• 左边元素 $\le pivot$；
• 右边元素 $\ge pivot$。

然后递归排序左右子序列。

2. 复杂度

情况	递推	复杂度
最好	$T(n)=2T(n/2)+\Theta(n)$	$\Theta(n\log n)$
平均	近似均衡分划	$\Theta(n\log n)$
最坏	$T(n)=T(n-1)+\Theta(n)$	$O(n^2)$

3. 改进方法

1. 随机选择主元；
2. 取首、中、尾三者中值作为主元；
3. 子序列足够小时改用插入排序；
4. 将递归算法改为非递归算法。

4. 排序下界

任何基于关键字比较的排序算法，最坏情况下至少需要：

$$\Omega(n\log n)$$

次比较。

---

5.6 选择问题 ⭐⭐⭐⭐

选择问题：在 $n$ 个元素中找第 $k$ 小元素。

1. 基于Partition的选择

分划后设左子表含主元的长度为 $p$：

• 若 $k=p$，主元就是第 $k$ 小；
• 若 $k<p$，在左子表找第 $k$ 小；
• 若 $k>p$，在右子表找第 $k-p$ 小。

随机主元：

• 平均时间 $O(n)$；
• 最坏时间 $O(n^2)$。

2. 线性时间选择

采用“中位数的中位数”选择主元，递推可写成：

$$T(n)\le T(n/5)+T(3n/4)+cn$$

结论：

$$T(n)=O(n)$$

---

5.7 Strassen矩阵乘法 ⭐⭐

普通分治需要 8 次子矩阵乘法：

$$T(n)=8T(n/2)+O(n^2)=O(n^3)$$

Strassen将乘法减少为 7 次：

$$T(n)=7T(n/2)+O(n^2)=\Theta(n^{\log_2 7})\approx \Theta(n^{2.81})$$

记住结论即可，公式不一定全背，但应知道“7次乘法代替8次乘法”。

---

第5章练习题与答案

练习5-1

分治法适用的三个条件是什么？

答案：可分解为相互独立的同类子问题；小规模子问题可直接求解；子问题解能合并为原问题解。

练习5-2

二分搜索的递推式和复杂度是什么？

答案：

$$T(n)=T(n/2)+\Theta(1)=\Theta(\log n)$$

练习5-3

归并排序和快速排序的Combine步骤分别是什么？

答案：归并排序的Combine是线性合并两个有序子序列；快速排序的Combine是空操作，因为分划后左右递归排好即整体有序。

练习5-4

快速排序最坏情况何时出现？

答案：每次主元都选到当前序列最小或最大元素，导致规模分解为 $0$ 和 $n-1$，复杂度退化为 $O(n^2)$。

练习5-5

求最大最小元，普通扫描和分治法比较次数分别是多少？

答案：普通扫描为 $2(n-1)$；当 $n=2^k$ 时，分治法为 $3n/2-2$。

练习5-6

Strassen算法为什么比普通矩阵乘法快？

答案：普通分治每层需要8次规模为 $n/2$ 的矩阵乘法，Strassen只需要7次，递推指数从3降为 $\log_2 7\approx2.81$。

---

第6章 贪心法 ⭐⭐⭐⭐⭐

6.1 贪心法一般方法 ⭐⭐⭐⭐⭐

贪心法用于求解最优化问题。
每一步做当前看起来最优的选择，希望最终得到整体最优解。

基本概念：

概念	含义
可行解	满足约束条件的解
目标函数	衡量解优劣的函数
最优解	使目标函数取最大或最小的可行解
最优量度标准	每一步选择依据，也称贪心准则
可行性判定函数	判断加入新元素后是否仍可行

通用伪代码：

Solution Greedy(A, n) {
    solution = empty;
    for (int i = 0; i < n; i++) {
        x = Select(A);
        if (Feasible(solution, x))
            solution = Union(solution, x);
    }
    return solution;
}

贪心法设计步骤：

1. 将问题看作一系列决策；
2. 确定每一步的局部最优准则；
3. 证明局部最优能导出全局最优。

必背：贪心算法不一定总能得到最优解，必须证明贪心选择性质和最优子结构。

---

6.2 背包问题 ⭐⭐⭐⭐⭐

1. 一般背包问题（可分割）

解向量：

$$X=(x_0,x_1,\dots,x_{n-1}),\quad 0\le x_i\le1$$

约束：

$$\sum w_ix_i\le M$$

目标：

$$\max \sum p_ix_i$$

贪心准则：

按单位重量收益 $p_i/w_i$ 非增排序，优先装单位价值高的物品。

复杂度主要来自排序：

$$O(n\log n)$$

定理：若

$$p_0/w_0\ge p_1/w_1\ge\cdots\ge p_{n-1}/w_{n-1}$$

则按该顺序贪心装入得到最优解。

2. 0/1背包问题（不可分割）

$x_i\in{0,1}$，物品只能整件选或不选。
贪心法一般不能保证最优，因为物品不可分割，可能造成剩余容量浪费。

考试常问：一般背包可用贪心，0/1背包通常用动态规划、回溯或分枝限界。

---

6.3 带时限的作业排序 ⭐⭐⭐⭐

1. 问题描述

单机系统，每个作业运行时间均为1。
作业 $i$ 有截止期限 $d_i$ 和收益 $p_i$。
若作业在期限内完成，则获得收益。目标是最大化总收益。

2. 贪心策略

1. 按收益 $p_i$ 非增排序；
2. 依次考虑作业；
3. 若加入后仍能在截止期限内完成，则选择该作业。

可行性判定：
将已选作业按截止期限非降排序，若第 $j$ 个作业满足：

$$d_{\alpha_j}\ge j+1$$

则该排序可行。

3. 并查集改进

朴素可行性检查可达 $O(n^2)$。
使用并查集记录可用时间片，可将时间接近降到线性级别。

---

6.4 最佳合并模式 ⭐⭐⭐⭐

问题：将 $n$ 个长度不同的有序子文件两两合并成一个文件，使总读写记录数最少。

贪心准则：

每次选择两个长度最小的文件合并。

这与哈夫曼树完全对应：

• 文件长度 = 外结点权值；
• 合并代价 = 带权外路径长度；
• 最优合并模式 = 最优二叉合并树/哈夫曼树。

K路合并：

• 每次选 $K$ 个最小权值合并；
• 若 $(n-1)\bmod(K-1)\ne0$，需补充若干零权值虚结点；
• 补充数量：

$$(K-1)-(n-1)\bmod(K-1)$$

最多 $K-2$ 个。

---

6.5 最小代价生成树 MST ⭐⭐⭐⭐⭐

1. 概念

无向连通图的生成树：包含全部结点，边数为 $n-1$，且连通无环。
最小代价生成树：所有生成树中边权和最小者。

2. MST性质（割性质）

设 $U$ 是 $V$ 的真子集，若边 $(u,v)$ 是所有连接 $U$ 与 $V-U$ 的边中权值最小者，则存在一棵MST包含该边。

Prim和Kruskal都基于这一性质。

3. Prim算法

贪心准则：

每次选一条连接“树内结点”和“树外结点”的最小边。

适合稠密图。
邻接矩阵实现复杂度：

$$O(n^2)$$

4. Kruskal算法

贪心准则：

按边权从小到大选边，只要不形成回路就加入。

使用并查集判断回路。
复杂度：

$$O(e\log e)$$

---

6.6 Dijkstra单源最短路径 ⭐⭐⭐⭐⭐

1. 适用条件

带权有向图或无向图，边权必须非负。
若存在负权边，Dijkstra不能保证正确。

2. 核心数据结构

数组	含义
d[i]	源点 $s$ 到结点 $i$ 的当前最短路径长度
path[i]	当前最短路径上 $i$ 的前驱
inS[i]	结点 $i$ 是否已加入最短路径集合 $S$

3. 算法步骤

1. 初始化 $S={s}$；
2. 在 $V-S$ 中选择 $d[k]$ 最小的结点 $k$ 加入 $S$；
3. 用 $k$ 松弛其他结点：

$$d[j]=\min\{d[j],d[k]+w(k,j)\}$$

若更新，则：

$$path[j]=k$$

1. 重复直到所有可达结点处理完。

邻接矩阵实现复杂度：

$$O(n^2)$$

---

6.7 磁带最优存储 ⭐⭐⭐

1. 单带最优存储

有 $n$ 个程序，长度为 $a_i$，每次检索前磁带都倒回最前端。
若检索概率相等，平均检索时间与程序排列的前缀长度和有关。

贪心准则：

按程序长度非降序存放。

即短程序放前面，使平均检索时间最小。

2. 多带最优存储

有 $m$ 条磁带，先按程序长度非降序排序，然后轮流分配：

$$程序 i \rightarrow 磁带 (i\bmod m)$$

这样可使总检索代价最小。

---

6.8 贪心法证明模板 ⭐⭐⭐⭐⭐

贪心正确性通常证明两点：

1. 贪心选择性质：存在一个最优解包含当前贪心选择；
2. 最优子结构：做出贪心选择后，剩余问题的最优解能与当前选择组合成原问题最优解。

常用证明方法：

① 设 O 是任意一个最优解。
② 若 O 已包含贪心选择，继续讨论子问题。
③ 若 O 不包含贪心选择，构造 O'：用贪心选择替换 O 中某个元素。
④ 证明 O' 仍可行，且目标函数不变差。
⑤ 因此存在一个包含贪心选择的最优解。
⑥ 对剩余子问题递归/归纳证明。

---

第6章练习题与答案

练习6-1

为什么0/1背包不能直接用单位价值贪心保证最优？

答案：因为物品不可分割，单位价值最高的选择可能占用容量后留下无法利用的剩余空间，导致总收益不如其他组合。

练习6-2

一般背包中，$M=20$，物品重量 $(18,15,10)$，收益 $(25,24,15)$。按贪心法求最优收益。

答案：单位价值分别为 $25/18\approx1.39$、$24/15=1.6$、$15/10=1.5$。排序为物品1、物品2、物品0。
先取物品1：重量15，收益24，剩余5。
再取物品2的一半：收益 $15\times 5/10=7.5$。
总收益：

$$31.5$$

练习6-3

带时限作业排序为什么要按收益非增顺序考虑？

答案：目标是最大化收益。按收益从高到低尝试，若可行则保留。正确性可用交换论证证明：若某最优解不含当前可行的高收益作业，可用该作业替换某个低收益作业且不降低总收益。

练习6-4

文件长度为 $5,10,20,30$，求两路最佳合并总代价。

答案：每次合并最小两个：

1. $5+10=15$；
2. $15+20=35$；
3. $30+35=65$。

总代价：

$$15+35+65=115$$

练习6-5

Prim和Kruskal分别适合什么图？

答案：Prim用邻接矩阵时适合稠密图；Kruskal按边排序，适合稀疏图，常配合并查集。

练习6-6

Dijkstra为什么要求边权非负？

答案：Dijkstra一旦选择当前 $d$ 最小的结点加入 $S$，就认为其最短距离已确定。若存在负权边，之后可能通过负边得到更短路径，破坏该贪心选择的正确性。

练习6-7

多带最优存储如何分配程序？

答案：先按程序长度非降序排序，再将程序 $i$ 放到第 $i\bmod m$ 条磁带上。

---

第7章 动态规划法 ⭐⭐⭐⭐⭐

7.1 动态规划基本要素 ⭐⭐⭐⭐⭐

动态规划适合求解具有以下两个性质的问题：

性质	含义
最优子结构	原问题最优解包含子问题最优解
重叠子问题	不同子问题会反复用到相同的小子问题

动态规划基本步骤：

1. 刻画最优解的结构特性；
2. 递归定义最优解值；
3. 自底向上计算最优解值；
4. 根据计算信息构造一个最优解。

DP vs 分治 vs 贪心

方法	子问题关系	是否依赖子问题解做选择	常见实现
分治	子问题相互独立	不一定	递归
贪心	每步只看当前最优	不依赖未来和子问题解	迭代
动态规划	子问题重叠	依赖子问题解	表格/备忘录

---

7.2 多段图问题 ⭐⭐⭐

多段图是带权有向图，结点分成 $k$ 段，边只从第 $i$ 段指向第 $i+1$ 段。目标是求源点 $s$ 到汇点 $t$ 的最短路径。

定义：

$$COST(i,j)=\text{从第 }i\text{ 段结点 }j\text{ 到汇点 }t\text{ 的最短路径长度}$$

递推思想：

$$COST(i,j)=\min_{(j,v)\in E}\{c(j,v)+COST(i+1,v)\}$$

边界：

$$COST(k,t)=0$$

同时记录决策 $D(i,j)$，用于回溯构造最短路径。

---

7.3 每对结点间最短路径 ⭐⭐⭐

PPT中该节标注“略”，但若考试涉及，通常考 Floyd 算法。

状态：

$$d^{(k)}[i][j]$$

表示只允许经过编号不超过 $k$ 的中间结点时，$i$ 到 $j$ 的最短路径。

递推：

$$d^{(k)}[i][j]=\min\{d^{(k-1)}[i][j],d^{(k-1)}[i][k]+d^{(k-1)}[k][j]\}$$

复杂度：

$$O(n^3)$$

---

7.4 矩阵连乘 ⭐⭐⭐⭐⭐

1. 问题

给定矩阵序列：

$$A_0A_1\cdots A_{n-1}$$

矩阵乘法满足结合律，不同加括号方式会导致不同数乘次数。目标是找最少数乘次数。

2. 状态定义

$$m[i][j]=A_iA_{i+1}\cdots A_j\text{ 的最少数乘次数}$$

3. 递推式

若最后一次断开在 $k$：

$$m[i][j]=\min_{i\le k<j}\{m[i][k]+m[k+1][j]+p_i p_{k+1}p_{j+1}\}$$

边界：

$$m[i][i]=0$$

记录：

$$s[i][j]=\text{最优断点}$$

用于构造最优加括号方案。

复杂度：

$$O(n^3)$$

空间：

$$O(n^2)$$

4. 备忘录方法

备忘录方法是自顶向下的动态规划：
递归求解子问题，并把已经求过的 $m[i][j]$ 存起来，避免重复计算。

---

7.5 最长公共子序列 LCS ⭐⭐⭐⭐⭐

1. 定义

序列 $Z$ 是 $X$ 的子序列：存在严格递增下标序列，使 $Z$ 中元素按顺序出现在 $X$ 中。
LCS是两个序列的最长公共子序列。

2. 状态定义

$$c[i][j]=X_1\cdots X_i\text{ 与 }Y_1\cdots Y_j\text{ 的LCS长度}$$

3. 递推式

边界：

$$c[i][0]=c[0][j]=0$$

若：

$$x_i=y_j$$

则：

$$c[i][j]=c[i-1][j-1]+1$$

否则：

$$c[i][j]=\max\{c[i-1][j],c[i][j-1]\}$$

记录方向：

方向	含义
左上	当前字符匹配，输出该字符
上	来自 $c[i-1][j]$
左	来自 $c[i][j-1]$

复杂度：

$$O(mn)$$

---

7.6 最优二叉搜索树 OBST ⭐⭐⭐

1. 问题

给定有序关键字：

$$a_1<a_2<\cdots<a_n$$

成功搜索概率为 $p(i)$，失败搜索概率为 $q(i)$。
目标是构造平均搜索时间最小的二叉搜索树。

2. DP思想

若 $a_k$ 为根，则：

• 左子树包含 $ai,\dots,a{k-1}$；
• 右子树包含 $a_{k+1},\dots,a_j$。

状态：

• $c[i][j]$：子树的最小成本；
• $w[i][j]$：概率权值和；
• $r[i][j]$：最优根。

递推核心：

$$c[i][j]=w[i][j]+\min_{i<k\le j}\{c[i][k-1]+c[k][j]\}$$

---

7.7 0/1背包动态规划 ⭐⭐⭐⭐⭐

1. 问题

物品不可分割：

$$x_i\in\{0,1\}$$

目标：

$$\max \sum p_ix_i,\quad \sum w_ix_i\le M$$

2. 离散容量DP

定义：

$$f[i][j]=前i件物品在容量j下的最大收益$$

递推：

若 $j\ge w_i$：

$$f[i][j]=\max\{f[i-1][j],f[i-1][j-w_i]+p_i\}$$

若 $j<w_i$：

$$f[i][j]=f[i-1][j]$$

边界：

$$f[0][j]=0,\quad f[i][0]=0$$

复杂度：

$$O(nM)$$

3. 连续数据/阶跃点方法

PPT中还提到阶跃点集合：

• $S_{-1}={(0,0)}$；
• $Si$ 由 $S{i-1}$ 与加入第 $i$ 件物品后的集合合并；
• 删除被支配点和 $X>M$ 的点。

最坏情况下时间和空间复杂度均可达：

$$O(2^n)$$

---

7.8 流水作业调度 ⭐⭐

PPT目录列出“流水作业调度”，正文未展开。若课堂补充，常见考法是两台机器流水作业的 Johnson 法则：

1. 对每个作业有两台机器加工时间 $a_i,b_i$；
2. 若 $\min(a_i,b_i)=a_i$，尽量排前；
3. 若 $\min(a_i,b_i)=b_i$，尽量排后；
4. 目标常是最小化总完成时间。

本节建议作为了解题，重点仍是矩阵连乘、LCS、0/1背包。

---

第7章练习题与答案

练习7-1

动态规划适用的两个基本要素是什么？

答案：最优子结构和重叠子问题。

练习7-2

动态规划和贪心法的主要区别是什么？

答案：贪心每步选择只依赖当前状态，不依赖子问题解；动态规划的选择依赖相关子问题的最优解，因此通常先求子问题，再决定最优选择。

练习7-3

写出矩阵连乘的状态和递推式。

答案：

$$m[i][j]=A_i\cdots A_j\text{ 的最少数乘次数}$$ $$m[i][j]=\min_{i\le k<j}\{m[i][k]+m[k+1][j]+p_ip_{k+1}p_{j+1}\}$$

边界 $m[i][i]=0$。

练习7-4

若 $X=ABCBDAB$，$Y=BDCABA$，LCS长度是多少？举出一个LCS。

答案：LCS长度为4。一个LCS是 BCBA，另一个常见答案是 BDAB。

练习7-5

写出0/1背包DP递推式。

答案：

若 $j\ge w_i$：

$$f[i][j]=\max\{f[i-1][j],f[i-1][j-w_i]+p_i\}$$

否则：

$$f[i][j]=f[i-1][j]$$

练习7-6

为什么矩阵连乘具有最优子结构？

答案：若 $Ai\cdots A_j$ 的最优加括号方式最后在 $k$ 处分开，则左边 $A_i\cdots A_k$ 和右边 $A{k+1}\cdots A_j$ 必须分别也是最优的，否则替换成更优子结构会得到更少乘法次数，矛盾。

练习7-7

Floyd算法的时间复杂度是多少？

答案：三重循环，时间复杂度为 $O(n^3)$。

---

第8章 回溯法 ⭐⭐⭐⭐

8.1 回溯法一般方法 ⭐⭐⭐⭐⭐

回溯法适合解可表示为 $n$ 元组的问题：

$$X=(x_1,x_2,\dots,x_n)$$

其中每个 $x_i$ 取自有限集合 $S_i$。

1. 基本概念

概念	含义
显式约束	规定每个 $x_i$ 可取值范围
隐式约束	判断候选解是否可行
解空间	所有满足显式约束的候选解集合
状态空间树	描述解空间的树结构
解状态	从根到该结点路径代表一个候选解
答案状态	从根到该结点路径代表一个可行解
目标函数/代价函数	衡量可行解优劣

2. 剪枝函数

剪枝函数	用途
约束函数	剪去不满足约束的子树
限界函数	剪去不可能产生最优解的子树

二者统称为剪枝函数。

3. 回溯法 vs 分枝限界法

方法	生成方式	常用场景
回溯法	深度优先生成状态空间树	找可行解或所有解
分枝限界法	广度优先或最小代价优先生成	找最优解

4. 递归回溯模板

void RBacktrack(int k) {
    for (每个可选 x[k]) {
        if (满足约束函数) {
            if (形成可行解)
                输出或更新答案;
            else
                RBacktrack(k+1);
        }
    }
}

5. 复杂度

回溯算法最坏情况可能达到：

$$O(p(n)n!),\quad O(p(n)2^n),\quad O(p(n)n^n)$$

其中 $p(n)$ 是生成一个结点所需的多项式时间。

---

8.2 n皇后问题 ⭐⭐⭐⭐⭐

1. 问题

在 $n\times n$ 棋盘上放置 $n$ 个皇后，使任意两个皇后不在同一行、同一列、同一斜线。

2. 解表示

用 $n$ 元组：

$$X=(x_0,x_1,\dots,x_{n-1})$$

其中 $x_i$ 表示第 $i$ 行皇后所在列。

显式约束：每行选一列。
若不允许同列，则状态空间为排列树，叶子数为 $n!$。

3. 冲突判定

两个皇后在 $(i,j)$ 和 $(k,l)$：

• 同列：$j=l$；
• 同一斜线：

$$|j-l|=|i-k|$$

Place函数核心：

bool Place(int k) {
    for (int i = 0; i < k; i++)
        if (x[i] == x[k] || abs(x[i]-x[k]) == abs(i-k))
            return false;
    return true;
}

---

8.3 子集和数问题 ⭐⭐⭐⭐

1. 问题

给定 $n$ 个不同正数 $w_i$ 和目标 $M$，求所有子集，使元素和为 $M$。

2. 解表示

固定长度：

$$X=(x_0,x_1,\dots,x_{n-1}),\quad x_i\in\{0,1\}$$

$x_i=1$ 表示选择 $w_i$。

也可以用可变长度元组记录被选元素下标或值。

3. 剪枝思想

设当前和为 $s$，剩余和为 $r$，下一个元素为 $w_k$：

• 若 $s=M$，输出答案；
• 若 $s+w_k>M$，选 $w_k$ 可能越界；
• 若 $s+r<M$，即使全选也达不到 $M$，剪枝。

---

8.4 图的m着色 ⭐⭐⭐⭐

1. 问题

给定无向图 $G=(V,E)$ 和 $m$ 种颜色，问是否能给每个结点着一种颜色，使任意相邻结点颜色不同。

2. 解表示

$$X=(x_0,x_1,\dots,x_{n-1}),\quad x_i\in\{1,\dots,m\}$$

$x_i$ 表示结点 $i$ 的颜色。

显式约束：$x_i$ 取颜色集合。
隐式约束：

$$若(i,j)\in E,\quad x_i\ne x_j$$

解空间大小：

$$m^n$$

---

8.5 哈密顿环 ⭐⭐⭐

1. 问题

给定 $n$ 个结点的连通图，找一条回路，它从某结点出发，经过每个结点恰好一次，最后回到起点。

2. 解表示

$$X=(x_0,x_1,\dots,x_{n-1})$$

$x_i$ 表示路径上的第 $i$ 个结点。

约束：

1. $x_i$ 互不相同；
2. $(xi,x{i+1})\in E$；
3. $(x_{n-1},x_0)\in E$。

---

8.6 回溯法求0/1背包 ⭐⭐⭐⭐

0/1背包是最优化问题，除约束函数外还需要限界函数。

1. 约束函数

若当前重量 $cw$，当前考虑物品 $k$：

$$cw+w_k\le M$$

则可以进入左子树（选择物品 $k$）。

2. 限界函数

设当前收益为 $cp$，当前已知最优收益下界为 $L$ 或 fp。
用可分割背包的贪心方法估计当前结点可能达到的收益上界 $bp$。

若：

$$bp<L$$

则该结点子树不可能产生更优解，可以剪枝。

PPT提醒：通常要求物品按单位价值 $p_i/w_i$ 非增排序。

---

8.7 批处理作业调度 ⭐⭐⭐

1. 问题

有 $n$ 个作业，每个作业需要依次在两台设备 $P_1,P_2$ 上加工。
作业 $i$ 在两台设备上的处理时间分别为 $a_i,b_i$。
目标是找到调度方案，使所有作业完成时间之和最小。

2. 回溯求解

解空间：作业的排列树，共 $n!$ 个叶子。
用当前部分调度的完成时间和进行剪枝：

若当前部分排列的完成时间和已经超过当前最优上界 $U$，则剪去该分枝。

---

第8章练习题与答案

练习8-1

什么是显式约束和隐式约束？

答案：显式约束规定每个分量的取值范围，形成候选解空间；隐式约束判断候选解是否满足问题要求、是否为可行解。

练习8-2

回溯法和分枝限界法的主要区别是什么？

答案：回溯法通常深度优先生成状态空间树；分枝限界法通常广度优先或按优先级生成结点。回溯多用于找可行解/全部解，分枝限界多用于最优化问题。

练习8-3

n皇后中，若两个皇后在 $(i,j)$ 和 $(k,l)$，如何判断是否在同一斜线？

答案：

$$|j-l|=|i-k|$$

练习8-4

图m着色的隐式约束是什么？

答案：若边 $(i,j)\in E$，则两个端点颜色不同，即 $x_i\ne x_j$。

练习8-5

哈密顿环和普通环的区别是什么？

答案：哈密顿环必须经过图中每个结点恰好一次，并最后回到起点；普通环没有这个要求。

练习8-6

0/1背包回溯中限界函数的作用是什么？

答案：估计当前结点子树可能达到的最大收益上界。若上界仍小于当前已知最优值，则该子树不可能产生最优解，可剪枝。

练习8-7

批处理作业调度的解空间通常是什么树？

答案：排列树，因为一个调度方案对应作业的一种排列。

---

综合练习题库（含答案）⭐⭐⭐⭐⭐

一、选择/判断题

1. 判断：贪心算法只要每一步选当前最优，就一定能得到全局最优。

答案：错误。必须证明贪心选择性质和最优子结构。

2. 判断：动态规划一定要求子问题相互独立。

答案：错误。子问题相互独立更适合分治；动态规划适用于重叠子问题。

3. 判断：Dijkstra算法可以处理负权边。

答案：错误。Dijkstra要求边权非负。

4. 判断：无向图DFS中只会出现树边和反向边。

答案：正确。

5. 判断：快速排序最坏时间复杂度为 $O(n\log n)$。

答案：错误。最坏为 $O(n^2)$。

---

二、计算题

1. 主方法

求：

$$T(n)=9T(n/3)+n^2$$

答案：

$a=9,b=3,E=\log_3 9=2$，$f(n)=n^2=\Theta(n^E)$。

$$T(n)=\Theta(n^2\log n)$$

2. 最佳合并模式

文件长度为 $2,3,5,7,11$，求最优合并总代价。

答案：

1. $2+3=5$；
2. $5+5=10$；
3. $7+10=17$；
4. $11+17=28$。

总代价：

$$5+10+17+28=60$$

3. 0/1背包DP

容量 $M=5$，物品重量 $(2,3,4)$，收益 $(3,4,5)$，最大收益是多少？

答案：

可行组合：

• 物品1：收益3；
• 物品2：收益4；
• 物品3：收益5；
• 物品1+2：重量5，收益7。

最大收益为：

$$7$$

---

三、简答题

1. 写出DP算法设计四步骤。

答案：

1. 刻画最优解结构；
2. 递归定义最优解值；
3. 自底向上计算最优解值；
4. 根据记录信息构造最优解。

2. 写出贪心正确性的常用证明思路。

答案：设任一最优解，若不含贪心选择，则用贪心选择替换其中某个元素，证明替换后仍可行且目标值不变差。因此存在包含贪心选择的最优解，再对子问题归纳证明。

3. 回溯法为什么能减少搜索量？

答案：回溯法在生成状态空间树时使用约束函数和限界函数剪枝，提前排除不可能产生可行解或最优解的子树，避免穷举全部候选解。

4. 分治法和动态规划的本质区别是什么？

答案：分治法将问题划分为相互独立的子问题，分别递归求解再合并；动态规划适用于子问题重叠的情况，通过保存子问题结果避免重复计算。

5. MST性质是什么？

答案：设 $U$ 是 $V$ 的真子集，若边 $(u,v)$ 是所有连接 $U$ 与 $V-U$ 的边中权值最小者，则存在一棵最小生成树包含该边。

---

四、算法设计模板题

1. 用动态规划设计算法时，答题模板是什么？

答案：

① 定义状态：dp[i][j] 表示什么；
② 写边界条件；
③ 写递推方程；
④ 说明填表顺序；
⑤ 若要求构造解，说明如何回溯；
⑥ 分析时间和空间复杂度。

2. 用回溯法设计算法时，答题模板是什么？

答案：

① 说明解向量形式；
② 写显式约束；
③ 写隐式约束/约束函数；
④ 若是最优化问题，写限界函数；
⑤ 给出搜索过程；
⑥ 分析最坏复杂度和剪枝作用。

3. 用贪心法设计算法时，答题模板是什么？

答案：

① 说明问题的解结构和目标函数；
② 给出贪心准则；
③ 写可行性判定；
④ 给出算法步骤；
⑤ 证明贪心选择性质和最优子结构；
⑥ 分析复杂度。

---

期末最后背诵版 ⭐⭐⭐⭐⭐

1. 必背复杂度

算法	时间复杂度
二分搜索	$\Theta(\log n)$
归并排序	$\Theta(n\log n)$
快速排序	平均 $\Theta(n\log n)$，最坏 $O(n^2)$
分治最大最小	比较次数 $3n/2-2$
随机选择	平均 $O(n)$，最坏 $O(n^2)$
线性选择	$O(n)$
Strassen	$\Theta(n^{2.81})$
Prim邻接矩阵	$O(n^2)$
Kruskal	$O(e\log e)$
Dijkstra邻接矩阵	$O(n^2)$
Floyd	$O(n^3)$
矩阵连乘	$O(n^3)$
LCS	$O(mn)$
0/1背包DP	$O(nM)$
n皇后回溯	最坏 $\Omega(n!)$ 级别
图m着色	最坏 $O(m^n)$ 级别

2. 必背递推式

问题	递推
二分搜索	$T(n)=T(n/2)+\Theta(1)$
归并排序	$T(n)=2T(n/2)+\Theta(n)$
快排最好	$T(n)=2T(n/2)+\Theta(n)$
快排最坏	$T(n)=T(n-1)+\Theta(n)$
Strassen	$T(n)=7T(n/2)+O(n^2)$
矩阵连乘	$m[i][j]=\min{m[i][k]+m[k+1][j]+pip{k+1}p_{j+1}}$
LCS	匹配：$c[i][j]=c[i-1][j-1]+1$；不匹配：取上/左最大
0/1背包	$f[i][j]=\max{f[i-1][j],f[i-1][j-w_i]+p_i}$

3. 最容易混淆的点

易混点	正确记忆
一般背包 vs 0/1背包	可分割用贪心；不可分割一般不用贪心
分治 vs DP	分治子问题独立；DP子问题重叠
贪心 vs DP	贪心当前选择；DP依赖子问题最优解
回溯 vs 分枝限界	回溯DFS；分枝限界BFS/优先队列
BFS vs DFS	BFS队列；DFS栈/递归
Prim vs Kruskal	Prim扩点；Kruskal选边
伸展树复杂度	单次最坏不一定 $O(\log n)$，分摊 $O(\log n)$
Dijkstra适用条件	边权非负
关节点判定	根看孩子数，非根看 $Low[w]\ge d[u]$

---

考前速记口诀

大O上界，Ω下界，Θ夹中间；
分治三步：分解、求解、合并；
贪心三问：准则是什么、是否可行、为何最优；
动态规划四件套：状态、边界、转移、回溯；
回溯两把剪刀：约束剪不可行，限界剪不最优；
DFS看时间戳，关节点看Low；
MST看割边，Dijkstra看非负；
LCS看左上上左，背包看选与不选。

---

---

手写代码题高频模板 ⭐⭐⭐⭐⭐

这些模板按“考试手写”整理：短、好背、能覆盖核心逻辑。
真正答题时，代码后最好补一句：算法思想 + 时间复杂度 + 关键边界条件。

---

1. 二分搜索模板 ⭐⭐⭐⭐⭐

适用：有序数组查找。

int BinarySearch(int a[], int n, int x) {
    int l = 0, r = n - 1;

    while (l <= r) {
        int mid = l + (r - l) / 2;

        if (a[mid] == x)
            return mid;
        else if (a[mid] < x)
            l = mid + 1;
        else
            r = mid - 1;
    }

    return -1;
}

必写说明：

每次比较后搜索区间减半，因此时间复杂度为 O(log n)。
前提是数组有序。

易错点：

• 循环条件是 l <= r；
• 更新时要写 mid + 1 或 mid - 1；
• mid = l + (r-l)/2 防溢出。

---

2. 分治求最大最小元模板 ⭐⭐⭐⭐

适用：分治法基础代码题。

void MaxMin(int a[], int l, int r, int &mx, int &mn) {
    if (l == r) {
        mx = mn = a[l];
    }
    else if (l + 1 == r) {
        if (a[l] < a[r]) {
            mx = a[r];
            mn = a[l];
        } else {
            mx = a[l];
            mn = a[r];
        }
    }
    else {
        int mid = (l + r) / 2;
        int mx1, mn1, mx2, mn2;

        MaxMin(a, l, mid, mx1, mn1);
        MaxMin(a, mid + 1, r, mx2, mn2);

        mx = max(mx1, mx2);
        mn = min(mn1, mn2);
    }
}

必写说明：

左右分别求最大最小，再合并。
时间复杂度 O(n)。
当 n=2^k 时比较次数为 3n/2-2。

---

3. 归并排序模板 ⭐⭐⭐⭐⭐

适用：分治排序，稳定排序。

void Merge(int a[], int l, int mid, int r) {
    int temp[1000];
    int i = l, j = mid + 1, k = 0;

    while (i <= mid && j <= r) {
        if (a[i] <= a[j])
            temp[k++] = a[i++];
        else
            temp[k++] = a[j++];
    }

    while (i <= mid)
        temp[k++] = a[i++];

    while (j <= r)
        temp[k++] = a[j++];

    for (i = l, k = 0; i <= r; i++, k++)
        a[i] = temp[k];
}

void MergeSort(int a[], int l, int r) {
    if (l >= r)
        return;

    int mid = (l + r) / 2;
    MergeSort(a, l, mid);
    MergeSort(a, mid + 1, r);
    Merge(a, l, mid, r);
}

必写说明：

递推式 T(n)=2T(n/2)+O(n)，所以时间复杂度 O(nlogn)。
合并时相等元素先取左边，因此归并排序稳定。

---

4. 快速排序模板 ⭐⭐⭐⭐⭐

适用：分治排序，常考 Partition。

int Partition(int a[], int l, int r) {
    int pivot = a[l];

    while (l < r) {
        while (l < r && a[r] >= pivot)
            r--;
        a[l] = a[r];

        while (l < r && a[l] <= pivot)
            l++;
        a[r] = a[l];
    }

    a[l] = pivot;
    return l;
}

void QuickSort(int a[], int l, int r) {
    if (l >= r)
        return;

    int p = Partition(a, l, r);
    QuickSort(a, l, p - 1);
    QuickSort(a, p + 1, r);
}

必写说明：

Partition后，主元左边元素不大于主元，右边元素不小于主元。
平均时间复杂度 O(nlogn)，最坏时间复杂度 O(n^2)。

易错点：

• pivot 要提前保存；
• 最后必须 a[l] = pivot；
• 递归区间要排除主元位置。

---

5. BFS模板 ⭐⭐⭐⭐⭐

适用：无权图最短路径、层次遍历。

#include <queue>
#include <vector>
using namespace std;

const int N = 100;
vector<int> g[N];
bool vis[N];
int parent[N];

void BFS(int s) {
    queue<int> q;

    vis[s] = true;
    parent[s] = -1;
    q.push(s);

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i];

            if (!vis[v]) {
                vis[v] = true;
                parent[v] = u;
                q.push(v);
            }
        }
    }
}

必写说明：

BFS使用队列，按层扩展。
在无权图中，某结点第一次被访问时得到的路径就是最短路径。
邻接表时间复杂度 O(n+e)。

---

6. DFS模板 ⭐⭐⭐⭐⭐

适用：图遍历、连通分量、时间戳、回溯类搜索。

#include <vector>
using namespace std;

const int N = 100;
vector<int> g[N];
bool vis[N];
int parent[N];

void DFS(int u) {
    vis[u] = true;

    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];

        if (!vis[v]) {
            parent[v] = u;
            DFS(v);
        }
    }
}

带发现/完成时间版本

int color[N];       // 0白，1灰，2黑
int d[N], f[N];
int timer = 0;

void DFSVisit(int u) {
    color[u] = 1;
    d[u] = ++timer;

    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];

        if (color[v] == 0)
            DFSVisit(v);
    }

    color[u] = 2;
    f[u] = ++timer;
}

必写说明：

DFS使用递归栈，邻接表时间复杂度 O(n+e)。
若 d[u] < d[v] < f[v] < f[u]，则 v 是 u 的后裔。

---

7. Dijkstra模板 ⭐⭐⭐⭐⭐

适用：非负权图单源最短路径。

const int INF = 1000000000;
const int N = 100;

int w[N][N];
int d[N];
int path[N];
bool used[N];

void Dijkstra(int n, int s) {
    for (int i = 0; i < n; i++) {
        d[i] = w[s][i];
        used[i] = false;

        if (w[s][i] < INF && i != s)
            path[i] = s;
        else
            path[i] = -1;
    }

    d[s] = 0;
    used[s] = true;

    for (int i = 1; i < n; i++) {
        int u = -1;
        int minD = INF;

        for (int j = 0; j < n; j++) {
            if (!used[j] && d[j] < minD) {
                minD = d[j];
                u = j;
            }
        }

        if (u == -1)
            break;

        used[u] = true;

        for (int v = 0; v < n; v++) {
            if (!used[v] && w[u][v] < INF) {
                if (d[u] + w[u][v] < d[v]) {
                    d[v] = d[u] + w[u][v];
                    path[v] = u;
                }
            }
        }
    }
}

必写说明：

每次从 V-S 中选 d 值最小的结点加入 S，再用它松弛其他结点。
要求边权非负。
邻接矩阵实现时间复杂度 O(n^2)。

---

8. Prim最小生成树模板 ⭐⭐⭐⭐

适用：无向连通带权图，稠密图常用。

const int INF = 1000000000;
const int N = 100;

int w[N][N];
int lowcost[N];
int closest[N];
bool used[N];

int Prim(int n, int s) {
    int ans = 0;

    for (int i = 0; i < n; i++) {
        lowcost[i] = w[s][i];
        closest[i] = s;
        used[i] = false;
    }

    used[s] = true;

    for (int i = 1; i < n; i++) {
        int u = -1;
        int minCost = INF;

        for (int j = 0; j < n; j++) {
            if (!used[j] && lowcost[j] < minCost) {
                minCost = lowcost[j];
                u = j;
            }
        }

        if (u == -1)
            return -1;

        used[u] = true;
        ans += minCost;

        for (int v = 0; v < n; v++) {
            if (!used[v] && w[u][v] < lowcost[v]) {
                lowcost[v] = w[u][v];
                closest[v] = u;
            }
        }
    }

    return ans;
}

必写说明：

lowcost[v] 表示树外结点 v 到当前生成树的最小边权。
每次选择 lowcost 最小的树外结点加入。
时间复杂度 O(n^2)。

---

9. Kruskal最小生成树模板 ⭐⭐⭐⭐

适用：无向连通带权图，稀疏图常用。

#include <algorithm>
using namespace std;

const int N = 100;
const int M = 1000;

struct Edge {
    int u, v, w;
};

Edge edge[M];
int fa[N];

bool cmp(Edge a, Edge b) {
    return a.w < b.w;
}

int Find(int x) {
    if (fa[x] == x)
        return x;
    return fa[x] = Find(fa[x]);
}

int Kruskal(int n, int e) {
    for (int i = 0; i < n; i++)
        fa[i] = i;

    sort(edge, edge + e, cmp);

    int ans = 0;
    int cnt = 0;

    for (int i = 0; i < e; i++) {
        int fu = Find(edge[i].u);
        int fv = Find(edge[i].v);

        if (fu != fv) {
            fa[fu] = fv;
            ans += edge[i].w;
            cnt++;

            if (cnt == n - 1)
                break;
        }
    }

    if (cnt != n - 1)
        return -1;

    return ans;
}

必写说明：

Kruskal按边权从小到大选边，用并查集判断是否成环。
时间复杂度 O(e log e)。

---

10. 一般背包贪心模板 ⭐⭐⭐⭐

适用：物品可以分割的背包问题。

#include <algorithm>
using namespace std;

struct Item {
    double w, p, r;
};

bool cmp(Item a, Item b) {
    return a.r > b.r;
}

double GreedyKnapsack(Item item[], int n, double M) {
    for (int i = 0; i < n; i++)
        item[i].r = item[i].p / item[i].w;

    sort(item, item + n, cmp);

    double ans = 0;
    double rest = M;

    for (int i = 0; i < n; i++) {
        if (item[i].w <= rest) {
            rest -= item[i].w;
            ans += item[i].p;
        } else {
            ans += item[i].p * rest / item[i].w;
            break;
        }
    }

    return ans;
}

必写说明：

按单位重量收益 p/w 非增排序。
能整件装入就整件装入，最后一个物品可部分装入。
时间复杂度主要来自排序，为 O(nlogn)。

---

11. 最佳合并模式模板 ⭐⭐⭐⭐

适用：每次合并两个文件，总代价最小。

#include <queue>
#include <vector>
using namespace std;

int OptimalMerge(int a[], int n) {
    priority_queue<int, vector<int>, greater<int> > q;

    for (int i = 0; i < n; i++)
        q.push(a[i]);

    int ans = 0;

    while (q.size() > 1) {
        int x = q.top(); q.pop();
        int y = q.top(); q.pop();

        int z = x + y;
        ans += z;
        q.push(z);
    }

    return ans;
}

必写说明：

每次选两个最小文件合并，等价于哈夫曼树构造。
时间复杂度 O(nlogn)。

---

12. 矩阵连乘DP模板 ⭐⭐⭐⭐⭐

适用：求矩阵链最少数乘次数。

const int INF = 1000000000;
const int N = 100;

int m[N][N];
int s[N][N];
int p[N];

void MatrixChain(int n) {
    for (int i = 1; i <= n; i++)
        m[i][i] = 0;

    for (int len = 2; len <= n; len++) {
        for (int i = 1; i <= n - len + 1; i++) {
            int j = i + len - 1;
            m[i][j] = INF;

            for (int k = i; k < j; k++) {
                int cost = m[i][k] + m[k + 1][j]
                         + p[i - 1] * p[k] * p[j];

                if (cost < m[i][j]) {
                    m[i][j] = cost;
                    s[i][j] = k;
                }
            }
        }
    }
}

输出最优加括号：

void Print(int i, int j) {
    if (i == j) {
        cout << "A" << i;
        return;
    }

    cout << "(";
    Print(i, s[i][j]);
    Print(s[i][j] + 1, j);
    cout << ")";
}

必写说明：

m[i][j] 表示 Ai...Aj 的最少数乘次数。
枚举最后一次断开位置 k。
时间复杂度 O(n^3)，空间复杂度 O(n^2)。

---

13. LCS最长公共子序列模板 ⭐⭐⭐⭐⭐

适用：两个序列的最长公共子序列。

const int N = 100;

int c[N][N];
int b[N][N];  
// 1 左上，2 上，3 左

void LCS(string x, string y) {
    int m = x.length();
    int n = y.length();

    for (int i = 0; i <= m; i++)
        c[i][0] = 0;

    for (int j = 0; j <= n; j++)
        c[0][j] = 0;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (x[i - 1] == y[j - 1]) {
                c[i][j] = c[i - 1][j - 1] + 1;
                b[i][j] = 1;
            }
            else if (c[i - 1][j] >= c[i][j - 1]) {
                c[i][j] = c[i - 1][j];
                b[i][j] = 2;
            }
            else {
                c[i][j] = c[i][j - 1];
                b[i][j] = 3;
            }
        }
    }
}

输出一个LCS：

void PrintLCS(string x, int i, int j) {
    if (i == 0 || j == 0)
        return;

    if (b[i][j] == 1) {
        PrintLCS(x, i - 1, j - 1);
        cout << x[i - 1];
    }
    else if (b[i][j] == 2) {
        PrintLCS(x, i - 1, j);
    }
    else {
        PrintLCS(x, i, j - 1);
    }
}

必写说明：

若 xi == yj，则 c[i][j]=c[i-1][j-1]+1；
否则 c[i][j]=max(c[i-1][j], c[i][j-1])。
时间复杂度 O(mn)。

---

14. 0/1背包DP模板 ⭐⭐⭐⭐⭐

适用：物品不可分割，每件只能选或不选。

const int N = 100;
const int M = 1000;

int f[N][M];
int w[N], p[N];

int Knapsack01(int n, int cap) {
    for (int i = 0; i <= n; i++)
        f[i][0] = 0;

    for (int j = 0; j <= cap; j++)
        f[0][j] = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= cap; j++) {
            f[i][j] = f[i - 1][j];

            if (j >= w[i]) {
                f[i][j] = max(f[i][j],
                              f[i - 1][j - w[i]] + p[i]);
            }
        }
    }

    return f[n][cap];
}

必写说明：

f[i][j] 表示前 i 件物品在容量 j 下的最大收益。
第 i 件物品只有选或不选两种情况。
时间复杂度 O(nM)。

一维优化版

int dp[M];

int Knapsack01_OneDim(int n, int cap) {
    for (int j = 0; j <= cap; j++)
        dp[j] = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = cap; j >= w[i]; j--) {
            dp[j] = max(dp[j], dp[j - w[i]] + p[i]);
        }
    }

    return dp[cap];
}

易错点：

一维0/1背包必须倒序枚举容量，否则会重复使用同一件物品。

---

15. n皇后回溯模板 ⭐⭐⭐⭐⭐

适用：回溯法、排列树、约束函数。

#include <cmath>
using namespace std;

const int N = 20;

int x[N];
int n;
int cnt = 0;

bool Place(int k) {
    for (int i = 0; i < k; i++) {
        if (x[i] == x[k])
            return false;

        if (abs(x[i] - x[k]) == abs(i - k))
            return false;
    }

    return true;
}

void Backtrack(int k) {
    if (k == n) {
        cnt++;
        return;
    }

    for (int col = 0; col < n; col++) {
        x[k] = col;

        if (Place(k))
            Backtrack(k + 1);
    }
}

必写说明：

x[k] 表示第 k 行皇后所在列。
不同行天然满足，因为每层只放一行。
不同列条件：x[i] != x[k]。
不同斜线条件：abs(x[i]-x[k]) != abs(i-k)。

---

16. 子集和数回溯模板 ⭐⭐⭐⭐

适用：子集树，选择/不选择当前元素。

const int N = 100;

int w[N];
int x[N];
int n, M;

void SubsetSum(int k, int sum) {
    if (sum == M) {
        for (int i = 0; i < k; i++) {
            if (x[i])
                cout << w[i] << " ";
        }
        cout << endl;
        return;
    }

    if (k == n || sum > M)
        return;

    x[k] = 1;
    SubsetSum(k + 1, sum + w[k]);

    x[k] = 0;
    SubsetSum(k + 1, sum);
}

带剩余和剪枝：

void SubsetSum2(int k, int sum, int rest) {
    if (sum == M) {
        for (int i = 0; i < k; i++) {
            if (x[i])
                cout << w[i] << " ";
        }
        cout << endl;
        return;
    }

    if (k == n)
        return;

    if (sum + rest < M)
        return;

    if (sum + w[k] <= M) {
        x[k] = 1;
        SubsetSum2(k + 1, sum + w[k], rest - w[k]);
    }

    x[k] = 0;
    SubsetSum2(k + 1, sum, rest - w[k]);
}

必写说明：

左分支选择当前元素，右分支不选择当前元素。
若当前和超过 M 或当前和加剩余元素仍小于 M，则剪枝。

---

17. 图m着色回溯模板 ⭐⭐⭐⭐

适用：m叉树、图着色。

const int N = 100;

int g[N][N];
int color[N];
int n, m;
int cnt = 0;

bool Ok(int k) {
    for (int i = 0; i < n; i++) {
        if (g[k][i] && color[k] == color[i])
            return false;
    }

    return true;
}

void GraphColor(int k) {
    if (k == n) {
        cnt++;
        return;
    }

    for (int c = 1; c <= m; c++) {
        color[k] = c;

        if (Ok(k))
            GraphColor(k + 1);

        color[k] = 0;
    }
}

必写说明：

显式约束：color[k] ∈ {1,...,m}。
隐式约束：相邻顶点颜色不同。
最坏候选数量为 m^n。

---

18. 0/1背包回溯模板 ⭐⭐⭐⭐

适用：回溯法求最优解。

const int N = 100;

int n, M;
int w[N], p[N];
int x[N], bestx[N];
int cw = 0, cp = 0;
int bestp = 0;

void BacktrackKnapsack(int k) {
    if (k == n) {
        if (cp > bestp) {
            bestp = cp;
            for (int i = 0; i < n; i++)
                bestx[i] = x[i];
        }
        return;
    }

    if (cw + w[k] <= M) {
        x[k] = 1;
        cw += w[k];
        cp += p[k];

        BacktrackKnapsack(k + 1);

        cw -= w[k];
        cp -= p[k];
    }

    x[k] = 0;
    BacktrackKnapsack(k + 1);
}

必写说明：

左子树表示选择第 k 件物品，右子树表示不选择。
约束函数为 cw + w[k] <= M。
如果加入限界函数，可进一步剪去不可能超过 bestp 的子树。

---

代码题考场速记模板 ⭐⭐⭐⭐⭐

分治法

if (小规模)
    直接求解;
else {
    分解问题;
    递归求解子问题;
    合并子问题答案;
}

贪心法

按贪心准则排序;
solution = empty;

for (每个候选对象) {
    if (加入后仍可行)
        加入solution;
}

动态规划

初始化边界;

for (按规模从小到大枚举状态) {
    for (枚举决策) {
        dp[当前状态] = 最优值;
    }
}

回溯法

void Backtrack(int k) {
    if (到达叶子) {
        输出或更新最优解;
        return;
    }

    for (每个可选值) {
        做选择;
        if (满足约束/限界)
            Backtrack(k + 1);
        撤销选择;
    }
}

---

最可能手写的代码清单 ⭐⭐⭐⭐⭐

代码题	可能性	必背程度
二分搜索	高	⭐⭐⭐⭐⭐
归并排序	高	⭐⭐⭐⭐⭐
快速排序 Partition	高	⭐⭐⭐⭐⭐
BFS / DFS	高	⭐⭐⭐⭐⭐
Dijkstra	高	⭐⭐⭐⭐⭐
Prim / Kruskal	中高	⭐⭐⭐⭐
矩阵连乘	中高	⭐⭐⭐⭐
LCS	高	⭐⭐⭐⭐⭐
0/1背包DP	高	⭐⭐⭐⭐⭐
n皇后回溯	高	⭐⭐⭐⭐⭐
子集和 / 图着色	中高	⭐⭐⭐⭐
一般背包贪心	中	⭐⭐⭐⭐
最佳合并模式	中	⭐⭐⭐⭐

---