算法设计与分析这门课的期末试卷，几乎是每个计算机相关专业学生都要正面硬刚的一场硬仗。它不像数据结构那样偏重"你记不记得这个结构怎么操作"，也不像高等数学那样考计算熟练度——它考的是一种更"上层"的能力：给你一个从没见过的问题，你能不能在十几分钟内判断它该用分治、动态规划还是贪心，然后把状态定义、转移方程、复杂度一道推下来。很多人复习时把课件翻了三遍，一到考场上遇到"请设计一个 O(n log n) 的算法求解下列问题"就脑子空白，根本原因是没搞清这门课的命题逻辑。这篇东西我想从一个"做过题、带过人、也踩过坑"的角度，把算法设计与分析期末试卷这件事彻底拆开：它的考点地图长什么样，高频题型背后想考什么，计算题和设计题的标准解法套路是什么，以及考场上真正会失分的地方在哪里。不管你是在临时抱佛脚，还是想提前一学期把节奏铺好，这里的内容都能直接拿去用。
1. 试卷整体设计与命题思路拆解
1.1 这门课的知识地图到底铺了多宽
算法设计与分析的课程内容看着杂，其实主干非常清晰，就五根柱子：复杂度分析、算法设计范式、图算法、难解性与归约、以及工程化的算法选择。复杂度分析是所有题的地基，它决定了你后面每一个答案能不能自圆其说；设计范式是核心，通常包括分治、动态规划、贪心、回溯、分支限界、随机化这几类；图算法是应用最密集的一块，最短路、最小生成树、最大流、拓扑排序、强连通分量都在这；难解性部分讲 P、NP、NPC、NP-hard 以及多项式归约；最后一块经常被学生忽略，就是"给定场景选算法"的综合题。
期末试卷的覆盖面基本会照着这个地图走，但权重从来不是平均的。动态规划通常吃掉整张卷子 25% 到 35% 的分值，因为它是唯一一个既能考建模、又能考计算、还能考证明的范式；分治次之，主要考递归式求解和主定理；贪心往往和证明题绑定；图算法一般以一道大题的形式出现，要么手算表格，要么写伪代码；NP 部分通常是一道小题加一道归约证明，分值不高但极其容易翻车。
我的经验是，考前如果只有两天复习时间，你会想把 70% 的精力压在 DP 和图算法上——这两块的内容密度和出题频率，远高于其他章节。分治的递归式求解是"会了就拿分"的送分题，投入产出比极高，值得单独花两小时吃透。
1.2 一张典型卷子的题型结构与分值权重
把近几年不同院校的算法期末卷放一起对比，结构惊人地相似。下面这张表是我整理的"典型结构"，你可以拿去对照自己学校的卷子，看看哪里被加强、哪里被弱化。
| 题型 | 常见分值 | 主要考查能力 | 拿分难度 |
|---|---|---|---|
| 选择/填空 | 15-20 分 | 概念记忆、复杂度常识 | 低，但要细心 |
| 简答/名词解释 | 10-15 分 | 定义复述与理解 | 低 |
| 计算题 | 20-30 分 | 手算流程、递归式、表格填充 | 中 |
| 算法设计题 | 25-35 分 | 建模、伪代码、复杂度分析 | 高 |
| 证明题 | 10-15 分 | 正确性、归约、最优子结构 | 高 |
| 编程/伪代码实现 | 5-10 分 | 落地能力 | 中 |
从这张表能读出一个很关键的信号：选择和填空加起来只占不到 20%，剩下的 80% 都是"你得动笔推"的题。这直接决定了复习策略——死背名词解释顶多保住及格线，真正拉开差距的是计算题和设计题能不能写出规范的过程。
另外一个细节是，很多卷子会在计算题里塞一道"陷阱题"，比如给一个不满足主定理条件的递归式，或者给一个用贪心会出错、必须用 DP 的背包变种。这类题的用意不是刁难，而是筛掉那些只会套模板、不理解适用条件的人。
1.3 命题背后的能力分层逻辑
我更愿意把这张卷子理解成一个四层的过滤器，每一层对应一种能力，分值也大致按这个梯度往上走。
第一层是记忆层，考渐进记号的严格定义、各种排序的稳定性、常见算法的时间复杂度。这一层的题几乎不需要思考，属于"你看过就能答"。
第二层是理解层，考你知不知道某个算法的前提假设。比如 Dijkstra 为什么不能处理负权边，Floyd 为什么能处理负权但不能处理负权环，Kruskal 依赖的并查集为什么能做到近似常数时间。这一层开始需要解释"为什么"，而不是"是什么"。
第三层是应用层，也就是设计题的主战场。给你一个具体场景，比如"某仓库有一排货架，每次能搬走相邻的一段……"，让你判断这是区间调度、背包还是编辑距离的变体，然后建状态、写转移。
第四层是分析层，包括正确性证明、复杂度下界、多项式归约。这一层考的是"你能不能说服阅卷人你的算法是对的"，也是最容易只写结论不给理由、被扣掉一半分的地方。
说实话，我见过太多人卡在第三层和第四层之间：他其实能写出正确的 DP 转移方程，但让他在答案里解释"为什么这个状态定义是完备的"，就说不出来了。阅卷老师哪怕知道他答案对，也会因为过程缺失扣分。
2. 核心考点细节解析与高频陷阱
2.1 复杂度分析：定义证明才是真考点
渐进记号那套定义，几乎所有卷子都会考，但形式非常固定。你要把五个记号的定义背到条件反射的程度：O 是存在 c 和 n₀ 使得对所有 n ≥ n₀ 有 f(n) ≤ c·g(n)；Ω 是不等号反向；Θ 是两者同时成立；小 o 要求的是对任意常数 c 都成立，且通常要求 c 可以任意小；小 ω 同理反向。
题目最喜欢的形式是"用定义证明 3n² + 5n + 7 = Θ(n²)"。标准写法是：取 c₁ = 3、c₂ = 15、n₀ = 1，然后分别证明上下界。这里有个细节很多人栽：n₀ 的选择不是唯一的，你只要给出一个可行的就行，但必须显式给出。我见过有同学写了一大堆不等式推导，最后忘了写"取 n₀ = 1"，硬生生被扣分。
还有个高频陷阱是"渐进复杂度不等于实际快慢"。两个都是 O(n log n) 的算法，常数因子可能差三倍。卷子上如果问"下列算法中最坏情况下最优的是"，通常比的是渐进阶；但如果问"实际运行更快的是"，就得考虑输入规模和常数了。审题时把这两种表述区分清楚，比多背两个公式有用得多。
2.2 主定理与递归式：会解和不会解的分水岭
分治题的灵魂是递归式求解。主定理给的是三种情况，判断依据是比较 f(n) 和 n^(log_b a) 的大小关系。我把这个判断流程整理成一张速查表，考场上可以照着走。
| 比较关系 | 情形 | 结果 | 例子 |
|---|---|---|---|
| f(n) 多项式地小于 n^(log_b a) | 情况一 | T(n) = Θ(n^(log_b a)) | T(n)=8T(n/2)+n² |
| f(n) 与 n^(log_b a) 同阶 | 情况二 | T(n) = Θ(n^(log_b a) · log n) | T(n)=2T(n/2)+n |
| f(n) 多项式地大于，且满足正则条件 | 情况三 | T(n) = Θ(f(n)) | T(n)=2T(n/2)+n² |
"多项式地"这三个字是判断的关键。如果 f(n) 只比 n^(log_b a) 大一个 log 因子，比如 T(n) = 2T(n/2) + n log n，主定理的三种情况都不适用，你得改用递归树或代入法，答案是 Θ(n log² n)。这种题专门用来筛只会套公式的人，遇到的时候千万别硬套，直接在答案里说明"主定理不适用，改用递归树"，然后画树、分层求和，反而能拿全分。
代入法（也叫猜测-验证法）的规范写法是三步：先猜出解的形式，再代入递归式验证，最后用归纳法证明边界成立。很多人只猜不证，或者猜完代进去算对了就收笔，实际上证明部分才是这道题的分所在。
2.3 动态规划：状态定义决定了你 80% 的分数
DP 题的评分标准很现实：状态定义写对，得分就过半；转移方程写对，基本满分；过程再规范点，就是高分。反过来，状态定义错了，后面写得再长都是零分。
我把 DP 的解题过程固化成五个动作，考场上按顺序做就行。第一步是判断有没有最优子结构和重叠子问题，这两个条件缺一不可，缺了就该换范式。第二步是定义状态，通常用 f[i] 表示"以第 i 个元素结尾的最优值"或 f[i][j] 表示"前 i 个和前 j 个的最优匹配"。第三步是写出转移方程，这一步要覆盖所有决策分支，不能漏。第四步是确定边界条件和填表顺序，比如 0-1 背包必须倒序枚举容量，LCS 必须按行或按列从小到大填。第五步是给出答案所在的格子，很多人算完整个表却答错了最终值的位置。
几个高频模型的转移方程必须背熟：
- 最长公共子序列（LCS）：如果两个字符相等，f[i][j] = f[i-1][j-1] + 1；否则 f[i][j] = max(f[i-1][j], f[i][j-1])。
- 0-1 背包：f[j] = max(f[j], f[j-w[i]] + v[i])，容量维度倒序。
- 最长递增子序列：O(n²) 版本是 f[i] = 1 + max{f[j] | j < i 且 a[j] < a[i]}；O(n log n) 版本用 tail 数组做二分。
- 矩阵链乘：m[i][j] = min{ m[i][k] + m[k+1][j] + p[i-1]·p[k]·p[j] }，按链长从小到大填。
坑最多的是0-1 背包和完全背包的枚举顺序。这个区别不是死记硬背能解决的，得理解：倒序是为了保证每个物品只被用一次，正序会让同一件物品被重复放入。卷子上如果把"每件物品无限件"和"每件物品一件"混在一道题里考，八成就是冲着这个知识点来的。
2.4 贪心：写对了算法不等于拿到了分
贪心题最容易被低估。很多同学写出一个看起来正确的贪心策略就收笔了，结果证明题部分一分没拿。这里的关键认知是：贪心算法的正确性不是显而易见的，必须用交换论证（exchange argument）或拟阵理论来证。
交换论证的标准结构是三步。先假设存在一个最优解 OPT，然后找出 OPT 与贪心解 G 的第一个不同决策，把 OPT 里的那个选择换成 G 的选择，证明换完之后解不会变差，最后用归纳法说明可以一直换下去，直到 OPT 变成 G。听起来抽象，但落到具体题上非常套路化，比如区间调度题，交换论证的核心就是"最优解里第一个结束的区间，一定能换成贪心选的那个最早结束的区间，且不影响后续选择"。
判断一道题能不能用贪心，经验上有两个信号：一是问题有没有"选择后不影响后续"的性质（也就是贪心选择性质），二是能不能找到一个反例。后者更实用——考试前你如果能记住几个经典反例，比如"0-1 背包不能用贪心（反例：容量 10，物品 (6, 6)、(5, 5)、(5, 5)）"，遇到类似题就能立刻判断该用 DP。
下面这张表是我归纳的"该用哪个范式"的判断依据，做题时可以先扫一遍。
| 问题特征 | 首选范式 | 典型题目 |
|---|---|---|
| 可分解为独立子问题，子问题不重叠 | 分治 | 归并排序、快排、最近点对 |
| 子问题重叠，需要最优子结构 | 动态规划 | 背包、LCS、编辑距离 |
| 有贪心选择性质，局部最优即全局最优 | 贪心 | 区间调度、Huffman、最小生成树 |
| 解空间是树形结构，需要剪枝 | 回溯/分支限界 | N 皇后、TSP、装载问题 |
| 规模大、允许近似，精确解太难 | 近似算法 | 顶点覆盖、TSP 近似 |
2.5 图算法与 NP 归约：两道高频证明题
图算法的手算题几乎必考。Dijkstra 的表格填充、Floyd 的三重循环矩阵更新、Prim 和 Kruskal 的边选择过程、拓扑排序的出队顺序，这些都是"按流程走就能拿分"的题。但有两个地方特别容易出错。
第一个是Dijkstra 手算时忘记更新 dist 数组的松弛条件。规范做法是每一步都画出 dist 表和"已确定集合 S"，每一步只把当前最近的未确定点加入 S，然后用它松弛邻居。考官看的不是你的最终答案，而是你的过程有没有体现松弛操作。
第二个是Floyd 的三重循环顺序。k 必须放最外层，因为它的物理含义是"允许经过的中间点集合逐步扩大"。如果你把 k 放到最内层，算法含义就变了，这是常见错误。
NP 归约题的套路非常固定。题目通常给两个问题 A 和 B，让你证明 A ≤ₚ B 或者证明某个问题是 NP-hard。归约的方向是最容易搞混的地方：要证明 B 是 NP-hard，你需要找一个已知的 NP-hard 问题 A，把 A 归约到 B，也就是"A 的任意实例都能在多项式时间内转成 B 的一个实例，且答案一致"。方向写成 B 归约到 A 就完全反了，这道题直接归零。
典型归约链要记住：3-SAT → 团问题 → 顶点覆盖 → 集合覆盖 → 哈密顿回路 → TSP。这条链上任意两个节点之间的归约，考试都有可能让你补一段。我的建议是至少把"3-SAT 归约到团"这个经典构造背下来，因为它的构造手法（用子句和文字构造图）是很多题目的模板。
3. 完整试卷模拟与逐步拆解
接下来这部分是实战。我按一套 100 分的标准卷来写，题目难度参照多数院校的中上水平，每题都给出答案和必要的解题过程。你可以先自己写，再对答案。
3.1 选择题与填空题（附解析）
题目 1：下列关于渐进记号的表述，正确的是（ ） A. 如果 f(n) = O(g(n))，那么 g(n) = O(f(n)) B. 如果 f(n) = Θ(g(n))，那么 f(n) = O(g(n)) 且 f(n) = Ω(g(n)) C. 如果 f(n) = o(g(n))，那么 f(n) = Θ(g(n)) D. n log n = O(n)
答案：B。A 显然错，反例是 n = O(n²) 但 n² ≠ O(n)；C 把小 o 和 Θ 搞混了；D 的 n log n 增长速度超过 n，不成立。
题目 2：关于 Dijkstra 算法，下列说法正确的是（ ） A. 可以处理负权边 B. 时间复杂度在用二叉堆优化下是 O((V+E) log V) C. 只能求单源最短路，不能求全源最短路 D. 相当于对图做一次广度优先搜索
答案：B。A 是经典陷阱，负权边会让"已确定"的最短路被推翻；C 表述本身看着对，但其实可以用它跑 V 次求全源；D 只在边权全为 1 时成立。
题目 3：以下问题中，属于 NP 完全的是（ ） A. 排序 B. 单源最短路 C. 0-1 背包的判定版本 D. 最大流
答案：C。0-1 背包的判定版本是 NP 完全的，而它的最优化版本是 NP-hard。这里要特别注意"判定版本"和"最优化版本"的区别，很多卷子就考这个点。
题目 4：用主定理求解 T(n) = 4T(n/2) + n，结果是（ ） A. Θ(n²) B. Θ(n log n) C. Θ(n² log n) D. Θ(n)
答案：A。这里 a=4，b=2，n^(log₂4) = n²，f(n) = n 多项式地小于 n²，属于情况一，结果是 Θ(n²)。
3.2 计算题：矩阵链乘的手算填表
题目：给定矩阵链 A₁A₂A₃A₄，维度分别为 10×20、20×5、5×40、40×25，求最优加括号方式和最小乘法次数。
解题过程：先把维度数组写成 p = [10, 20, 5, 40, 25]，p[i-1] × p[i] 是第 i 个矩阵的行列数。然后按链长 L 从 2 到 4 依次填表。链长为 2 时，m[1][2] = 10×20×5 = 1000，m[2][3] = 20×5×40 = 4000，m[3][4] = 5×40×25 = 5000。链长为 3 时，m[1][3] 要比较 k=1 和 k=2 两种情况，k=1 时代价为 m[1][1] + m[2][3] + 10×20×40 = 0 + 4000 + 8000 = 12000，k=2 时代价为 m[1][2] + m[3][3] + 10×5×40 = 1000 + 0 + 2000 = 3000，取小的 3000。
链长为 4 时，m[1][4] 比较三个 k 值。k=1：m[1][1] + m[2][4] + 10×20×25，其中 m[2][4] 需要先算出来。这里就体现出填表顺序为什么必须是按链长递增——外层循环枚举链长，才能保证计算 m[i][j] 时所有更短的子链都已经算好。最终结果是 m[1][4] = 11000，最优加括号方式是 (A₁)((A₂A₃)A₄) 或类似形式，具体看 s 表的记录。
注意：这道题的手算过程一定要把 m 表和 s 表都画出来，光写一个最终答案通常只能拿一半分，因为阅卷是按过程给分的。
3.3 算法设计题：从场景到状态定义
题目：某物流站有一排共 n 个包裹，第 i 个包裹重量为 w[i]、价值为 v[i]。现在有一辆容量为 C 的车，每个包裹要么装要么不装，求能装走的最大总价值。
这题就是标准的 0-1 背包。状态定义：f[j] 表示容量为 j 时能获得的最大价值。转移方程：对每个物品 i，倒序枚举 j 从 C 到 w[i]，执行 f[j] = max(f[j], f[j-w[i]] + v[i])。边界是 f[0..C] 全部初始化为 0。时间复杂度 O(nC)，空间复杂度 O(C)。
关键是要在答案里解释为什么用滚动数组而不是二维数组，以及为什么容量维度要倒序。前者是为了把空间从 O(nC) 降到 O(C)，后者是为了保证每件物品只被选中一次。这两句话写上去，就是区分"背模板"和"真懂"的地方。
Python 实现如下：
def knapsack_01(weights, values, capacity): n = len(weights) dp = [0] * (capacity + 1) for i in range(n): for j in range(capacity, weights[i] - 1, -1): # 倒序是关键 dp[j] = max(dp[j], dp[j - weights[i]] + values[i]) return dp[capacity] # 测试 w = [2, 3, 4, 5] v = [3, 4, 5, 6] print(knapsack_01(w, v, 8)) # 输出 103.4 证明题:贪心正确性的交换论证
题目：给定 n 个区间 [sᵢ, fᵢ]，选择尽可能多的互不重叠区间。按结束时间升序的贪心策略是否正确？证明你的结论。
这是经典的区间调度问题，贪心策略是正确的。证明用交换论证：假设 OPT 是一个最优解，且 OPT 中的区间按结束时间排列为 o₁, o₂, ..., oₖ。贪心解 G 的第一个区间是 g₁，它是所有区间中结束时间最早的。
因为 g₁ 的结束时间 ≤ o₁ 的结束时间，且 o₁ 是 OPT 中最早结束的，所以把 o₁ 换成 g₁ 之后，g₁ 与 o₂ 一定不重叠（因为 g₁ 结束得更早）。替换后的解仍然是合法解，且区间数量不变，所以也是最优解。接下来对剩余区间递归地用同样的论证，最终得到 G 和 OPT 数量相同，贪心正确。
提示：这道题的采分点是"两个关键性质"——g₁ 与后续区间不重叠，以及更早结束的区间对后续约束更弱。能写出这两句话，基本就是满分回答。
3.5 编程题：三个必写模板
编程题通常要求用伪代码或指定语言实现，下面给出三个最常考的模板，都属于"写出来就能拿分"的题。
最长公共子序列：
def lcs(a, b): m, n = len(a), len(b) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): if a[i - 1] == b[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) return dp[m][n]堆优化版 Dijkstra：
import heapq def dijkstra(graph, start): dist = {node: float('inf') for node in graph} dist[start] = 0 pq = [(0, start)] while pq: d, u = heapq.heappop(pq) if d > dist[u]: continue for v, w in graph[u]: if dist[u] + w < dist[v]: dist[v] = dist[u] + w heapq.heappush(pq, (dist[v], v)) return dist快速选择求第 k 小：
import random def quickselect(arr, k): if len(arr) == 1: return arr[0] pivot = random.choice(arr) left = [x for x in arr if x < pivot] mid = [x for x in arr if x == pivot] right = [x for x in arr if x > pivot] if k <= len(left): return quickselect(left, k) elif k <= len(left) + len(mid): return pivot else: return quickselect(right, k - len(left) - len(mid))这三个模板覆盖了 DP、图算法、分治三大块。写的时候要注意if d > dist[u]: continue这个剪枝不能省，有人写堆优化 Dijkstra 忘了这一步，会导致同一个点被反复入堆，理论复杂度退化。
4. 常见问题与排查技巧实录
4.1 失分点速查表
带过几轮复习之后，我发现学生翻车的点高度集中。下面这张表是我从作业和试卷里整理出来的，对号入座看看你中了几条。
| 症状 | 根因 | 纠正方法 |
|---|---|---|
| DP 状态定义写了但转移算错 | 没覆盖所有决策分支 | 每次写完转移，手动枚举小规模输入验算 |
| 贪心题只给策略不给证明 | 不知道证明是采分点 | 记住交换论证三步法，强制写进答案 |
| 复杂度分析只给结论 | 漏了 n₀ 和常数 c | 定义证明必须显式写出 c 和 n₀ |
| 归约方向写反 | 没搞清楚"谁归约到谁" | 记住：要证 B 难，就把已知难的 A 归约到 B |
| 主定理乱套 | 没检查"多项式地"这个条件 | 遇到带 log 的 f(n) 先怀疑主定理失效 |
| 手算最短路不画中间表 | 以为答案对就行 | 每步画 dist 表和 S 集合，过程给分 |
| 编程题超时 | 用了朴素实现 | 记住堆优化、滚动数组、埃氏筛这些常见优化 |
其中我觉得最值得展开讲的是"DP 状态定义写了但转移算错"。这不是能力问题，是习惯问题。我的做法是每次写完转移方程，都拿一个 3×3 或者 4×4 的小例子手动跑一遍，看看边界和值对不对。这个动作只要一分钟，能省掉后面二十分钟的返工。我见过太多人交卷后才意识到自己某个下标写反了。
4.2 考场时间分配与答题顺序
150 分钟的卷子，我的建议时间分配是这样的：选择填空 20 分钟，简答 15 分钟，计算题 40 分钟，算法设计题 50 分钟，证明题 20 分钟，检查 5 分钟。这个分配的底层逻辑是：把分值密度最高的题放在状态最好的时间段做。
具体操作上，我会先通读全卷，用铅笔在题号旁标注难度（一星到三星）。然后按"一星 → 二星 → 三星"的顺序做。不要按题号顺序硬推，因为前面一道卡壳的大题会严重影响后面的心态和时间。算法设计题就算一时想不出最优解，也可以先把暴力解法写上去，很多卷子对暴力解法给 30% 到 50% 的分，空着是零分。
还有一个很实际的技巧：证明题和设计题的答案要分层写。先写"我的思路是……"，再写"具体步骤……"，最后写"复杂度分析……"。分层的答案即使某一部分错了，阅卷老师也能清楚看到你哪部分是对的，按点给分。
4.3 从判卷视角看失分
我帮老师看过几轮卷子，站在判卷的位置会发现一些平时完全想不到的事。最典型的是：写得多的不一定得分高，写得有条理的一定得分高。有的同学把整页纸写满，推导七八行，但状态定义藏在中间某行，转移方程写在边上，阅卷老师得费劲找——这种情况下，即使全对也容易被误判。反过来，把"状态定义 / 转移方程 / 边界 / 复杂度"四行分点写清楚，老师扫一眼就给了满分。
其次是符号规范。用 f[i][j] 也好，用 dp[i][j] 也好，只要前后一致就行；但如果前面用 f、后面用 d，老师会怀疑你自己都没想清楚。下标的含义一定要在第一次出现时用一句话说明，比如"f[i][j] 表示 A 的前 i 个字符和 B 的前 j 个字符的最长公共子序列长度"。
最后透露一个规律：设计题的最后一小问通常是"分析你算法的时间复杂度"，这问分值不高但极容易拿。哪怕你前面的伪代码写得一般，只要复杂度分析写对，这一问的分就稳了。很多人在前面耗光时间，最后这一问空着，非常可惜。
4.4 复习路径与投入产出比
如果你现在距离考试还有两周以上，我建议按这个顺序推进。第一周铺基础：把复杂度分析、分治递归式、五大 DP 模型过一遍，每天手写两道计算题，重点是矩阵链乘、LCS、背包的填表。第二周攻专题：图算法一天（Dijkstra、Floyd、Prim、Kruskal、拓扑排序手算各两遍），NP 归约一天（背熟归约链和三个经典构造），贪心证明一天（交换论证写五遍直到形成肌肉记忆）。剩下的时间做两套完整模拟卷，严格计时。
如果只剩三天，那就把资源全部压在三个点上：递归式求解、DP 状态设计、Dijkstra 与 Floyd 手算。这三块加起来通常能覆盖 45% 到 55% 的分值，而且是"练了就有分"的类型。NP 归约如果时间实在不够，至少要背下"3-SAT 归约到团"这一个构造，因为它是很多变体的母题。
我个人在实际复习和帮别人复习的过程中发现，算法设计与分析这门课最大的敌人不是难度，而是"以为看懂了"。翻课件的时候每一页都眼熟，一合上书什么都写不出来，这是最危险的状态。判断自己有没有真懂，只有一个标准：拿一张白纸，不看书，把矩阵链乘的填表过程完整写出来，把区间调度的交换论证完整写出来，把 3-SAT 归约到团的图构造完整画出来。能独立完成这三件事，这张卷子你基本就稳了。做不出来的部分，就是你该补的地方——不用猜，白纸会告诉你答案。
