1. 这门课到底在考什么，先看2023期末讨论里都出现了哪些影子

每年期末前，总有同学到处搜“某某大学算法设计与分析期末原题”，我也不例外。拿到湖南大学2023年网传的那份期末题目讨论时，我第一反应不是去看具体答案，而是先把整份题目的考点分布拉了一个清单。看完之后有个很强烈的感受：题目可以千变万化，但核心考法非常固定，选择题、简答题、编程题基本都围绕那十几个经典模型在打转。

算法设计与分析这门课，和数据结构最大的区别在于：数据结构考你“这个东西怎么组织”，算法设计与分析考你“这个问题怎么解、为什么这么解、复杂度是多少”。期末试卷表面上是几个大题，实际上是在测你有没有建立一套算法思维。所谓算法思维，说白了就是三件事：第一，拿到问题能不能快速判断该用分治、动态规划、贪心还是回溯；第二，能不能把解决方案写得让机器执行，而不是只会背概念；第三，能不能说清楚这个方案的时间复杂度、空间复杂度，以及为什么它比其他方案好。

2023年的期末讨论里，选择题部分出现了很多复杂度比较的题，比如让你判断某个递归式对应的时间复杂度，或者比较不同排序算法在特定数据下的表现。这类题在哪个学校都逃不掉，因为复杂度分析是整个课程的骨架。简答题则集中在动态规划的两个核心性质、贪心算法与动态规划的区别、分支限界与回溯的异同这些老生常谈的点上。编程题部分，一眼扫过去就是0-1背包、最长公共子序列、最短路径、活动安排这几个经典模型的变体。

所以，不要被“原题”两个字带偏。真正有价值的不是记住某一道题怎么解，而是透过这些题目看到，老师想考核的知识点其实是一个封闭的集合。把这套知识点吃透了，任意换数字、换背景、换描述方式，你都能认出来它背后到底在考什么。

2. 把考点按优先级排序，别平均用力

2.1 动态规划永远站在C位

不管哪个学校的算法设计与分析试卷，动态规划都是绝对的大头，湖南大学2023年的讨论里同样如此。选择题会有状态转移方程的理解题，简答题会让你写出最优子结构和无后效性的定义，编程题更是直接来一道DP题。动态规划之所以被反复考，是因为它综合考察了问题建模能力、递推思维和编码实现能力，这三样恰恰是程序员最核心的基本功。

备考动态规划，我建议不要一上来就刷题，先把几个最经典的模型吃透：0-1背包、完全背包、最长公共子序列、最长递增子序列、矩阵连乘、编辑距离。这六个模型覆盖了绝大多数DP题的套路。比如最长公共子序列属于“双序列DP”，状态定义是dp[i][j]表示第一个序列前i个字符和第二个序列前j个字符的LCS长度；0-1背包属于“单序列+容量约束”的DP，状态定义是dp[i][j]表示前i个物品在容量为j的背包里能装的最大价值。你把这些模型的状态定义、初始化、转移方程、遍历顺序全部手写一遍，比看十遍课件都管用。

动态规划还有一个容易被忽略的点：不是所有最优子结构问题都能用DP，还要满足无后效性。我的理解是，无后效性就是说当前状态一旦确定，后续决策只与当前状态有关，不会去关心之前是怎么走到这个状态的。考试时如果问“为什么这道题可以用DP”，你要答出三点：问题具有最优子结构、无后效性、子问题重叠。少一个都不完整。

2.2 分治与递归，复杂度分析是送分题也是送命题

分治算法在期末考试里很少单独出大编程题，但它几乎是所有后续算法的地基。归并排序、快速排序、二分查找、大整数乘法、Strassen矩阵乘法，这些经典分治案例的递推式和时间复杂度，基本是选择题和简答题的常客。比如问你T(n)=2T(n/2)+O(n)的复杂度，答案就是O(nlogn)；T(n)=T(n/1)+O(1)就是O(logn)。这类题只要熟练掌握主定理，基本就是送分。

但很多人栽在细节上：主定理的三种情况分不清，递归式的边界条件忽略，或者把分治和动态规划搞混。我当年就犯过这个错误，看到“把大问题分解成小问题”就以为是分治，其实动态规划同样也是把大问题分解成子问题。两者的本质区别在于：分治的子问题是相互独立的，而动态规划的子问题会重叠。这个区别在简答题里特别容易考，一定要记准。

2.3 贪心、回溯与分支限界，常以对比的面目出现

贪心算法在期末卷面上通常作为编程大题出现，比如活动安排、最小生成树、单源最短路径的Dijkstra算法、哈夫曼编码。这些例子有个共同特点：每一步都做当前看起来最优的选择，且这个局部最优能推出全局最优。考试时如果出一道贪心题，很可能要求你证明贪心选择性质。很多同学只会写算法，不会证明，这是复习的大漏洞。其实证明思路很固定：先假设存在一个最优解，然后通过交换论证说明贪心选择不会使解变差，最后用数学归纳法或反证法收尾。

回溯和分支限界在编程题里出现的概率相对低一些，但在简答题里几乎每学期都有。要搞清楚四个关键差异：回溯是深度优先搜索所有解空间，分支限界是广度优先或最小耗费优先搜索；回溯的目标通常是找出所有解，分支限界的目标通常是找一个最优解；回溯用栈或递归实现，分支限界用队列或优先队列实现；回溯的剪枝函数只判断可行性，分支限界还需要考虑限界函数。把这张对比表背熟，简答题基本稳了。

2.4 图算法：期末卷面上的常青树

图算法在2023年的讨论里同样占了不少篇幅。Dijkstra、Floyd、Prim、Kruskal、拓扑排序、关键路径，这些都是高频考点。我的经验是，图算法题很少要求你从零发明算法，更多是考察你“会不会用代码实现经典算法”以及“能不能对手写例子手动模拟一遍算法过程”。所以备考时，光看懂PPT不够，一定要在纸上手动跑一遍Dijkstra的整个过程，把每个节点的dist值和前驱节点一个个写出来。

图算法还有一个容易踩的坑：使用场景混淆。Dijkstra不能处理负权边，Floyd可以处理负权边但不能有负权回路，Bellman-Ford可以检测负权回路，Prim适合稠密图，Kruskal适合稀疏图。这些边界条件记清楚，选择题才能不丢分。

3. 编程题实战：把经典模型变成肌肉记忆

3.1 0-1背包：从递归到DP，一个模型吃透动态规划

期末编程题如果考动态规划，0-1背包的变体出现频率极高。不要一上来就写二维DP，先试着用递归描述问题，然后改成记忆化搜索，最后再优化成DP，这个过程能帮你彻底理解状态转移。下面是一个最基础的0-1背包实现，语言用Python：

def knapsack(weights, values, capacity): n = len(weights) # dp[i][j] 表示前 i 个物品，背包容量为 j 时的最大价值 dp = [[0] * (capacity + 1) for _ in range(n + 1)] for i in range(1, n + 1): for j in range(capacity + 1): if weights[i - 1] <= j: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]) else: dp[i][j] = dp[i - 1][j] return dp[n][capacity]

这段代码里的状态转移方程是：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1])。含义是：当前第i个物品我有两种选择，不装进背包，那就继承前i-1个物品在容量j下的最优值；装进背包，那就腾出w[i-1]的空间，加上当前物品的价值。考试时如果编程题出背包，大概率不是让你原样写这个基础版，而是在物品数量、选择规则、约束条件上改一改。但只要你吃透了上面这个模板，认出来它是背包并不难。

还可以继续优化成一维数组，因为dp[i][j]只依赖dp[i-1]这一行。优化时有个关键点：容量j必须从大往小遍历，否则同一个物品会被重复选。这个细节特别适合考选择题和简答题，比如给出一个一维数组版本的代码，问为什么第二层循环要倒序遍历。答案很简单：正序遍历会把当前物品多次放入背包，等价于完全背包。

3.2 最短路径代码模板：Dijkstra和Floyd怎么选

图算法编程题里，最短路径是热门。考虑到考试时间限制，Dijkstra用优先队列实现是最稳妥的，既能跑稠密图也能跑稀疏图，代码量适中。下面是一份可以快速默写的模板：

import heapq def dijkstra(graph, start, n): # graph[u] = [(v, weight), ...] dist = [float('inf')] * n 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

写这道题的时候，有几个容易错的地方。第一，绿点判断可以省略，因为如果从堆里弹出的d已经大于dist[u]，说明这个节点已经被更新过了，直接跳过。第二，初始化时dist[start]=0，其他节点为正无穷，不能漏。第三，堆中元素是元组(dist, node)，排序会先按dist排，所以dist要放在前面。这三个点，任何一个搞错，程序都会出问题，或者逻辑对但效率低。

如果题目里要求任意两点之间的最短路径，而且边权可能为负，那就不要犹豫，用Floyd。Floyd的核心是一个三重循环：

def floyd(graph, n): # graph[i][j] 直接存储权重，不存在则设为 inf dist = [[graph[i][j] for j in range(n)] for i in range(n)] for k in range(n): for i in range(n): for j in range(n): if dist[i][k] + dist[k][j] < dist[i][j]: dist[i][j] = dist[i][k] + dist[k][j] return dist

很多同学问，Floyd的三层循环为什么k一定要放在最外层？我的理解是，k代表“允许经过的前k个节点”，这本身是一种从小到大递推的过程。如果把k放在内层，就变成了“某一次路径计算时允许经过某个节点”，这并不能保证全局最优，结果就会错。这个解释在考场上如果被问到，可以直接说：外层k本质是在枚举中间节点集合的规模，和DP中的阶段是一样的概念。

3.3 写代码前先写五分钟伪代码

考场上编程题最忌讳的是拿到题就敲代码。我记得当年有同学一上来就噼里啪啦写，写了一半发现状态定义不对，又全部擦掉，白白浪费十五分钟。我的习惯是，先用两三分钟在草稿纸上写出关键四件事：状态定义、初始化、转移方程、遍历顺序。对于图算法，再加上一个数据结构选择：是用邻接矩阵还是邻接表，是用数组模拟队列还是用优先队列。

这五分钟不会浪费。把伪代码写清楚之后，再往代码语言里翻译，出错率会低很多。还有一个小技巧：如果时间紧张，写代码时用变量名短一点没关系，但一定要让自己看得懂。考场上你是不需要给代码写注释的，但变量名最好能表达含义，比如dp、dist、prev，这样检查时方便，也方便老师判卷时读懂你的思路。万一最终代码有小bug，至少思路分能保住。

4. 简答题和概念题：背什么、怎么答才不丢分

4.1 P、NP、NPC这些概念，先把逻辑链条理清

算法设计与分析课程最后总会讲计算复杂性理论，这也是期末简答题的必考区。很多同学对P、NP、NPC的概念背了又忘，原因是没理解这条逻辑链。

P类问题指的是能在多项式时间内解决的问题，NP类问题指的是能在多项式时间内验证一个解是否正确的问题。注意，NP全称是Non-deterministic Polynomial，不是Non-Polynomial，这一点选择题特别爱挖坑。如果一个问题既能多项式时间求解，又想找一个多项式验证方法，它显然属于P，也属于NP。所以P类问题是NP类问题的子集，只不过学界至今没证明P是否等于NP。

NPC问题则是NP类问题里“最难”的一类，它的定义是：首先它属于NP，其次所有NP问题都能在多项式时间内归约到它。换句话说，只要有一个NPC问题能被多项式时间求解，那所有NP问题都能被多项式时间求解，P就等于NP了。期末如果让你举NPC问题，常见的有旅行商问题、三色图问题、哈密顿回路、子集和问题。把这些例子记熟，简答题至少能写出一半内容。

4.2 动态规划性质的表述要专业化

2023年的简答题里，动态规划的最优子结构和无后效性几乎是必问题。很多同学能说出大概意思，但表述不严谨，导致扣分。最优子结构的标准说法是：一个问题的最优解包含其子问题的最优解。无后效性的标准说法是：某阶段状态一旦确定，此后的决策只依赖当前状态，与之前如何到达该状态无关。

这里我提供一个答题模板：问“为什么该问题可以用动态规划求解”时，分三步答。第一步，指出问题具有最优子结构，并简单举例说明最优解中包含子问题的最优解；第二步，指出各阶段决策具有无后效性，当前状态即可描述未来决策所需的所有信息；第三步，指出子问题存在重叠，若用递归会有大量重复计算，因此用动态规划存储中间结果。这三步写下来，答案不仅完整，还能体现你是真的理解，而不是死记硬背。

4.3 对比题是送分题，但一定要写全对比维度

期末考试特别喜欢出对比类简答题，比如“回溯法与分支限界法的异同”“Dijkstra与Prim算法的区别”“动态规划与贪心算法的区别”。这类题的答题技巧是：不要只写一句“一个用DFS一个用BFS”，而是从目标、搜索方式、适用条件、数据结构、时间复杂度、典型应用等维度逐条对照。

比如动态规划与贪心算法，可以从三个维度答：适用条件上，DP要求最优子结构且子问题重叠，贪心要求贪心选择性质；求解方式上，DP自底向上或自顶向下求解所有子问题，贪心每一步只做一个局部最优决策；证明难度上，DP的证明一般依赖数学归纳法，贪心需要证明贪心选择的正确性，通常用交换论证。这样一对比，阅卷老师一眼就能看出你掌握了知识点。

5. 复习计划与考场时间分配，这是一场策略游戏

5.1 四周复习计划，按周拆解任务

期末复习最忌讳从头到尾看一遍课件。课件只是知识的索引，真正帮你提分的是动手写题。我建议把复习周期设为四周，每周一个主题，周末做一次综合自测。

第一周集中攻克复杂度分析和分治法，把所有递归式分析题做完，主定理的三种情况要烂熟于心。第二周全身心投入动态规划，把0-1背包、最长公共子序列、最长递增子序列、编辑距离等经典题自己亲手实现一遍，并试着不看题解讲出状态转移过程。第三周主攻贪心算法和图算法，重点手动模拟Dijkstra、Prim、Kruskal、拓扑排序的整体流程。第四周回归简答题和概念题，把P、NP、NPC、最优子结构、贪心选择性质这些概念梳理成自己的答题模板，每天默写一遍。

这里有个细节：每周的周末自测一定要计时，严格按照考试时间来做。不光是检验知识掌握程度，更是训练你在压力下做题的状态。很多同学平时写得很好，一到考场就慌，就是因为缺少限时模拟训练。自测完不必追求满分，重点看哪些题目卡了超过十分钟，这些卡顿点就是你下周需要补的漏洞。

5.2 考场上的时间分配，前松后紧最致命

我观察过很多期末卷面，发现不及格的同学通常不是不会做，而是时间分配出了问题。有的在前面的选择题上纠结太久，导致后面的编程题没时间写；有的在最后一道大题上死磕，结果前面简单题白白丢分。这里分享一套我的时间分配策略，适用于大多数算法考试。

假设考试时长120分钟，总分100分。选择题和填空题建议控制在25到30分钟内完成，这些题考察的是记忆和理解，会就会，不会就标记一下先跳过，千万不能恋战。简答题建议控制在30分钟内，每题写个四五行，条理清晰就行，不要长篇大论。剩下的60分钟留给编程题和算法设计题。拿到编程题，先用5分钟在草稿纸上列状态定义和转移方程，再用25分钟实现，最后留10分钟检查边界条件。

如果编程题写完之后还有时间，一定要回头检查自己标记过的选择题和填空题。往往就是在你头脑最清醒的时候，之前拿不准的题突然就有思路了。还有一点，如果编程题实在写不出来，不要空着，把你想到的状态定义、转移方程、甚至只是大致的算法框架都写上去。很多学校是按步骤给分的，一个正确的状态定义就能拿到宝贵的几分。

5.3 复习资料怎么用，原题不等于答案

回到文章开头的问题：搜到“湖南大学算法设计与分析2023期末考试原题”到底有没有用？我的答案是：有用，但用法不是背答案。原题最大的价值是帮你划出考点范围和出题风格，让你知道老师偏爱考哪类知识点、编程题爱用哪些经典模型做基底。拿到原题之后，你应该做的是把每一道题对应到教材的知识点，然后去找相同知识点的其他题目练习，而不是把原题答案背下来。

我一贯的看法是，算法这门课靠背是背不出来的。你背下了一道0-1背包题的代码，考试时出个完全背包变体，你还是得从头分析。相反，如果你真正理解了“状态定义”和“状态转移”这两个核心概念，无论题目怎么变换，你都能写出正确的代码。所以复习的时候，优先级永远是把原理搞懂，其次才是刷题，最后才是看原题。

6. 高频错题与避坑实录，这些细节决定了你能多拿十分

6.1 动态规划的三个常见坑

第一个坑是初始化不对。很多DP问题里，dp[0][j]和dp[i][0]这些边界值不是0，而是正无穷或负无穷，取决于你是求最小值还是最大值。比如编辑距离中，dp[0][j] = j，dp[i][0] = i，因为从一个空串变成长度为j的串需要j次插入操作。如果初始化时一律填0，结果就全错了。判断初始化是否正确，我的经验是手动验证一个最小的例子，比如dp[1][1]，看看它是否符合直觉。

第二个坑是遍历顺序不对。如果是一维DP，背包容量循环方向会决定是“每个物品只能选一次”还是“每个物品可以选很多次”，这一点上文已经说过了。如果是二维DP，遍历顺序对结果影响不大，但要注意状态依赖的是上一行还是本行左侧。比如说最长公共子序列里，dp[i][j]依赖dp[i-1][j]、dp[i-1][j-1]、dp[i][j-1]，那i和j都从前往后遍历就行；但如果是编辑距离，dp[i][j]也依赖dp[i-1][j-1]，同样从前往后遍历没问题。关键是动手前先画一张二维表，把每个格子的依赖关系画出来，遍历顺序就一目了然。

第三个坑是状态转移方程漏掉一种情况。比如最长递增子序列中，dp[i]表示以第i个元素结尾的最长递增子序列长度，它依赖所有满足j<i且a[j]<a[i]的dp[j]加1，最后取最大值。很多同学只写了一个“dp[i] = dp[i-1] + 1”，这是错的，因为递增子序列不一定连续，dp[i]和前一个元素不一定有直接关系。要想避开这个坑，拿到题先想一想：我当前这个状态到底能由哪些“前一个状态”转移过来，把所有可能性列全，再写方程。

6.2 图算法题里容易被忽略的边界

图算法编程题里，最常见的错误是用邻接矩阵但忘记处理重边。如果两个节点之间有多条边，邻接矩阵存储时应该保留最小权值，否则Dijkstra或Prim会拿到一个较大的边权，影响最短路径或最小生成树结果。邻接表则天然支持重边，但代价是遍历时可能多处理几条边。考场上如果你发现样例数据可以通过但提交却超时，可以先想想是不是图存储方式选错了。

另一个坑是节点编号从0开始还是从1开始。如果题目给的是1到n的节点，而你的数组长度是n，初始化dist数组时要给下标0留一个空位，或者干脆把所有下标减1统一成从0开始。这个问题看似低级，但每年都会有人因为下标越界而丢分。我的习惯是，代码里第一行就把“本代码所有节点统一从0开始”写进注释，然后所有数组都按n来开，不给自己留犯错的机会。

还有一个容易忽略的点：如果题目中的图不一定连通，Dijkstra之后未访问到的节点dist会被初始化为正无穷，输出时要按题目要求处理，比如输出-1。很多同学默认所有节点都能被访问到，结果输出了一堆inf，白白丢了测试点的分。预处理时先想想图是否连通、是否可能有孤立节点，这比盲目写代码更重要。

6.3 复杂度分析题，别忘记常数和log

复杂度分析的选择题和填空题，经常考一些“看似简单但容易算错”的题。常见的坑有三个：忽略循环条件中的乘除关系，把O(nlogn)写成O(n^2)；忽略递归式中每一项的规模，直接把T(n)=2T(n/2)+O(n)写成O(n)；忽略常数因子，把O(2n)和O(n)当成不同的复杂度。

关于最后一点，我特意提出来是因为很多初学者会误以为常数会影响大O结果。其实量级分析只看增长速度，2n和n都归为O(n)。考场上如果选择题问“以下哪个和O(n)等价”，千万别选“2n”这种选项，因为它是同一个量级，只是写法不同。至于递归式分析，最稳妥的方法是背熟主定理的三种情况，再结合手工展开验证一遍。熟练之后，你在考场上连草稿纸都不用翻就能写出答案。

6.4 用手写模拟代替纯脑补，是复习阶段最高效的方法

有些知识点，比如Dijkstra的过程、Prim的选边过程、拓扑排序的出队顺序，光看代码很难形成直觉。我强烈建议复习时准备一张白纸，手动跑一遍完整流程。以Dijkstra为例，把每个节点的dist值用一个表格列出来，每次选最小dist节点，更新邻居，然后在表格里划掉已确定的节点。整个过程手写三遍，你自然就理解了为什么已经弹出的节点不需要再更新。

这个方法对回溯算法同样有效。画一棵解空间树，从根节点出发，按DFS顺序遍历，标出哪些节点被剪枝、为什么被剪枝。当你能把一棵树的剪枝过程画得明明白白，分支限界和回溯的区别也就迎刃而解。很多时候我们觉得算法抽象，只是因为脑子里缺少一个可以依赖的图像。手写模拟就是把这个图像刻进脑子里最直接的方式，比抄十遍代码都管用。

7. 最后说一点关于“原题”的个人体会

我是支持大家去找原题的，但一定要带着脑子找。算法设计与分析这门课，核心考点就那么多，原题最大的作用其实是让你快速锁定复习范围，而不是让你投机取巧。我见过太多同学花三天时间背原题答案，结果考试时题目稍微换了个说法，连“这题考的是动态规划”都看不出来。反而是那些把经典模型踏踏实实练过几遍的人，即使没见过原题，也能从考场出来时心里有底。

最后再分享一个我踩过很多次坑之后总结的小技巧：考前最后一天，不要再做新题了。把你整理好的状态转移方程、图算法模板、复杂度分析方法一条一条默写出来，只看自己不熟悉的部分。真正到了考场上你就会发现，紧张感会消化的不是知识，而是信心。当你看到那道所谓的新题，脑子里能立刻蹦出“这不就是0-1背包一个变体嘛”的时候，你就已经在及格线之上了。