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背包实现语言用Pythondef 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] jdp[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个元素结尾的最长递增子序列长度它依赖所有满足ji且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背包一个变体嘛”的时候你就已经在及格线之上了。