1. 先把这门课的期末考“地图”画出来算法设计与分析的期末复习最忌讳的一件事就是一上来抱着教材从第一章啃到最后一章。我带过几届学弟学妹的考前突击也自己踩过一轮完整的坑最大的体会是这门课的考点密度极不均匀复习的收益差距可以拉开好几倍。同样花十个小时有人从及格冲到优秀有人还在递归式的下标上纠结。差别不在于聪不聪明而在于有没有先搞清楚“考什么、怎么考、我该先补哪块”。先说这门课的本质。算法设计与分析不是让你背代码它考的是三件事会不会算复杂度、会不会选策略、会不会证明正确性。三个能力对应三种题型也对应三条完全不同的复习路径。复杂度是地基任何一道题都可能让你写一个递推式策略是主干分治、动态规划、贪心、回溯、分支限界这五板斧几乎撑起全部设计题证明是分水岭是普通同学和拿高分同学之间最大的差距。网络热搜里反复出现的“湘潭大学算法设计与分析”“算法设计与分析期末编程题”“算法设计与分析期末题”其实指向同一个痛点大家最怕的是编程题和设计题而不是选择题。因为选择题勾错了损失两分编程题写不出来可能直接损失十几分。所以我这份复习笔记的权重分配是复杂度分析和策略选择占六成编程实现占三成证明套路占一成——但那一成往往是决定能不能上 90 分的部分。下面我会按“题型拆解 → 复杂度地基 → 五板斧逐个击破 → 代码模板 → 踩坑速查”的顺序往下讲。不管你基础如何建议至少把第 2 节和第 4 节读透这两块是性价比最高的。1.1 题型分布与分值权重的真实拆解不同学校的卷面结构差异挺大但底层逻辑是相通的。我把它归成五类并给出我观察到的常见权重范围题型常见占比典型考法复习优先级选择/填空/判断10%~20%概念辨析、复杂度比较、性质判断中计算分析题20%~30%写递推式、求渐进阶、画递归树、跑算法过程高算法设计题25%~35%给场景选策略写伪代码复杂度最高编程实现题15%~25%手写或机试完整可运行代码高证明题10%~20%贪心正确性、NP 归约、下界证明中高这张表你最好抄下来贴在复习计划本第一页。它的用法是当时间不够时优先保“算法设计题”和“计算分析题”因为这两块确定性最强、训练见效最快。选择题靠临考前几天刷概念就够了证明题则要在策略题练熟之后再回头补因为证明用的工具交换论证、归纳、归约本身就以策略理解为前提。还有一个容易被忽略的点计算分析题是唯一可以“无脑得分”的题型。写递推式、套主定理、画递归树这些都是机械动作练二十道就能形成肌肉记忆考场上几乎不会失分。而设计题需要一点灵感和经验积累证明题更是看临场发挥。所以复习节奏应该是先用计算题建立信心和手感再攻设计题最后扫证明题和概念题。1.2 复习顺序的取舍逻辑我个人的建议顺序是复杂度分析 → 动态规划 → 分治 → 贪心 → 回溯与分支限界 → 图算法 → NP 理论 → 概念扫尾。这个顺序不是教材顺序而是按“出现频率 × 学习曲线”排的。动态规划为什么排这么前因为它出现的频率最高而且和贪心、分治都有交叉是整门课的枢纽。把 DP 吃透你再看贪心就知道“为什么这里不能用 DP 而能用贪心”再看分治就知道“为什么这个递归式能合并”。分治排第三是因为它的数学建模递归式和复杂度分析直接打通学完第一二节马上就能练手。回溯和分支限界放在后面是因为它们在期末里通常只出一道题而且框架固定背模板就能拿分性价比属于“后期补分”型。NP 理论排最后是因为它抽象、容易混淆概念但考法固定判定 P/NP/NPC或者做一次简单归约不需要太多前置积累。提示如果你只剩三到五天把动态规划、分治、贪心这三块的核心例题各刷三遍性价比远超平均用力。2. 渐进复杂度分析所有题的地基这一节是整门课的地基。我发现很多同学做题卡壳不是不会设计算法而是写不出递推式、算不出复杂度导致明明思路对了却拿不到分。复杂度分析其实是一门“手艺”有固定的判定流程和套路。渐进符号一共五个考试里真正高频用的是 O、Ω、Θ 三个o 和 ω 偶尔出现在概念题里。它们的定义必须能背能推O 是上界Ω 是下界Θ 是紧确界o 是严格上界ω 是严格下界。考试里最常用的判定手法是取极限算 f(n)/g(n) 当 n 趋于无穷时的值是常数就 Θ是无穷就 ω 方向是零就 o 方向。常见函数阶的排序必须闭着眼都能排出常数 log n n^0.5 n n log n n² n³ 2^n n! n^n。别小看这个排序选择题里“下列函数中增长最快的是”这种题只要你记得住就秒答。有个口诀式记忆法“对数不如幂幂不如指数指数不如阶乘”反过来把幂的指数从小到大排就成。2.1 主定理三种情况的判断手法主定理是求递归式渐进阶最省力的工具但很多人用错根本原因是没搞清“比较对象”。递归式形如 T(n) a·T(n/b) f(n)其中 a ≥ 1b 1f(n) 是渐近正的函数。关键是拿 f(n) 和 n^(log_b a) 做比较情况一f(n) O(n^(log_b a − ε))说明递归部分占主导则 T(n) Θ(n^(log_b a))。情况二f(n) Θ(n^(log_b a) · log^k n)则 T(n) Θ(n^(log_b a) · log^(k1) n)。k0 时就是 Θ(n^(log_b a) · log n)。情况三f(n) Ω(n^(log_b a ε))且满足正则条件 a·f(n/b) ≤ c·f(n)c1则 T(n) Θ(f(n))。举个必考例子归并排序 T(n) 2T(n/2) n。这里 a2b2n^(log_2 2) nf(n) n两者同阶属于情况二k0所以 T(n) Θ(n log n)。再看二分查找 T(n) T(n/2) 1a1b2n^(log_2 1) n^0 1f(n)1同阶情况二T(n)Θ(log n)。正则条件是情况三最容易漏的地方。比如 T(n) 2T(n/2) n²n^(log_2 2)nf(n)n² 明显大于 n属于情况三验证正则条件2·(n/2)² n²/2 ≤ c·n²取 c0.5 成立所以 T(n)Θ(n²)。但如果 f(n) 增长得太“不规律”主定理就不适用了这时候要退回递归树或者代入法。2.2 递归树的画法与代入法验证主定理不适用的时候比如神秘的 T(n)T(n/3)T(2n/3)n递归树是万能解法。画递归树的步骤是每层列出该层所有子问题的代价之和然后求和所有层的代价。以 T(n)T(n/3)T(2n/3)n 为例。第一层代价 n第二层子问题规模 n/3 和 2n/3代价和还是 n第三层依然是 n……关键是看树什么时候停。最深的路径是沿 2n/3 这条分支每次乘 2/3直到降到常数深度是 log_{3/2} n。所以总共约 log_{3/2} n 层每层代价 nT(n)O(n log n)。这个用主定理算不了但递归树一眼就看出来。代入法用来“验证你猜的答案”。步骤是先猜一个阶再用数学归纳法证明。比如猜 T(n)O(n log n)假设对所有小于 n 的规模成立代入 T(n)2T(n/2)n ≤ 2·c·(n/2)·log(n/2)n cn·log n − cn n ≤ cn·log n当 c ≥ 1 时归纳成立。考场上如果时间紧代入法写个框架也能拿过程分。2.3 复杂度分析里最常踩的四个坑第一个坑把循环变量的变化方向搞反。比如for(i1; in; i*2)是 O(log n)但很多同学写成 O(n)。判断标准是“循环体执行次数”不是“n 的大小”。看到乘法或除法递进一律往 log 想看到加减递进往 n 想。第二个坑嵌套循环直接相乘。两层独立循环确实是 n×n但如果内层循环依赖外层的变量比如 j 从 i 开始就要做求和而不是相乘。经典例题for(i1;in;i) for(j1;ji;j)的总次数是 12...n n(n1)/2 O(n²)看着像相乘其实要精确求和才能拿到满分。第三个坑把 log 的底数当回事。log₂ n 和 log₁₀ n 只差常数倍在渐进符号下是同一个阶。所以答题时写 Θ(log n) 就够不用纠结底数除非题目明确要求具体数值。第四个坑忽略最好/最坏/平均的区别。快排最好 O(n log n)、最坏 O(n²)、平均 O(n log n)考场上问“快速排序的时间复杂度”一定要答三段只写一个可能被扣分。同理二分查找在有序数组上是 Θ(log n)但在链表上因为随机访问代价是 Θ(n)这个边界也要分清。注意主定理只适用于 T(n)aT(n/b)f(n) 这种“均匀划分”的形式。如果子问题规模不相等如 T(n)T(n−1)T(n−2)主定理无效必须用递归树或特征方程。3. 分治法从归并排序到最近点对分治法是五大策略里最“数学”的一个因为它和递归式、复杂度分析天然咬合。分治的核心思想是把大问题拆成规模更小的同型子问题分别求解后合并。它的三步走是Divide划分、Conquer解决、Combine合并。听起来简单但考场上真正难的是“怎么划分才能让合并这一步高效”。判断一道题能不能用分治看两个信号一是问题能自然二分数组、平面点集、矩阵二是子问题的解能在线性或接近线性时间内合并成原问题的解。如果合并代价太高比如 O(n²)分治反而比暴力慢这也是很多人误用分治的地方。3.1 分治递归式的建模方法分治算法的复杂度几乎都能写成 T(n) a·T(n/b) f(n) 的形式其中 a 是子问题个数b 是规模缩小的倍数f(n) 是划分和合并的代价。建模的关键是数清楚 a 和 b。归并排序每次二分成两个 n/2 的子问题合并需要 O(n) 的辅助数组操作所以 T(n)2T(n/2)n。二分查找只递归一侧a1b2比较代价 O(1)所以 T(n)T(n/2)1。快速排序平均情况下和归并类似但划分代价 O(n)、递归两边平均各 n/2所以平均 T(n)2T(n/2)n。有个特别好用的小技巧先写出 a、b、df(n) 的次数再套一张简化判定表。当 f(n)n^d 时关系复杂度实例d log_b aΘ(n^(log_b a))斯特拉森矩阵乘法d log_b aΘ(n^d · log n)归并排序、快排d log_b aΘ(n^d)朴素最大子段和分治的合并这张表其实就是主定理的简化版专门对付 f(n) 是幂函数的情况考场上比背完整主定理更快。3.2 五个分治经典例题拆解归并排序是分治的“Hello World”。要点是合并函数 merge两个已排序子数组双指针比较取小。归并的稳定性来自“相等时取左边”这个细节在问“哪些排序稳定”时是得分点。它的递归树高度 log n每层合并总代价 n所以 Θ(n log n)空间 O(n) 是它的软肋。最大子段和的分治解法是高频设计题。把数组从中间劈开最大子段要么全在左半、要么全在右半、要么跨越中点。前两种递归求解第三种从中点向两边各扫一遍求最大后缀和与最大前缀和代价 O(n)。所以 T(n)2T(n/2)O(n)O(n log n)。这里要特别注意分治解法不是最优的DP 可以做到 O(n)考试里如果题目问“最优”要答 DP如果问“用分治设计”再写分治。最近点对问题是分治里最优雅的例子也是典型的“合并比划分难”。按 x 坐标排序后二分左右各求最近距离 d₁、d₂取 dmin(d₁,d₂)。关键在于跨中线的点对只需考虑中线左右各宽 d 的带状区域且区域内每个点最多与后面 7 个点比较鸽巢原理保证所以合并代价 O(n)。整体 T(n)2T(n/2)O(n)O(n log n)。这里的“最多比 7 个点”是常考的证明细节一定要能说清为什么是常数个。棋盘覆盖考的是分治的构造思路。2^k × 2^k 的棋盘有一个特殊格用 L 型骨牌覆盖其余。做法是把棋盘四等分特殊格所在的那块继续递归另外三块的角上用一块 L 型骨牌人为制造“特殊格”于是四个子问题都有特殊格。递归式 T(n)4T(n/2)O(1)注意这里的 n 是边长解得 O(n²)正好等于骨牌数。快速排序的随机化版本也是分治但它的复杂度分析要用到期望。随机选主元保证期望划分平衡期望复杂度 O(n log n)。这个和确定性快排的“最坏 O(n²)”形成对比是选择题的常客。我的实操心得分治的递归式建模不要急着套主定理先把 a、b、f(n) 写在草稿纸上数错了后面全错。尤其是“子问题个数”a棋盘覆盖里 a4 不是 2最近点对里合并前是 a2这些细节决定成败。4. 动态规划状态定义才是命门如果整门课只能复习一块我选动态规划。它出现频率最高、题型最多变、也最能拉开分差。DP 的两大前提是最优子结构和重叠子问题最优子结构决定“能不能用 DP”重叠子问题决定“用了才划算”。很多人分不清 DP 和分治一句话概括分治的子问题相互独立不重叠DP 的子问题重叠需要记录。没有重叠还硬用 DP那就退化成普通递归白搭。DP 的复习有个反直觉的真相写状态转移方程只是最后一步真正的功夫在状态定义上。状态定义错了方程怎么写都不对状态定义对了方程几乎是自然涌现的。所以练 DP 的正确姿势是先问自己三个问题状态表示什么状态之间怎么转移边界和答案在哪4.1 从暴力递归到 DP 的三步推导我强烈推荐用“三步推导法”练 DP考场上也按这个顺序答题过程分稳稳的。第一步写暴力递归。先不考虑效率直接按问题定义写递归函数。比如 0-1 背包定义 f(i, c) 表示“前 i 件物品、容量为 c 时的最大价值”那么 f(i,c) max(f(i−1,c), f(i−1,c−w_i)v_i)边界是 i0 时返回 0。这一步哪怕指数级也要写出来因为它是后面两步的骨架。第二步加记忆化。把递归函数改成带备忘录的版本用数组或哈希表缓存已经算过的 (i,c)。这一步只是把重叠子问题“记住”复杂度立刻从指数降到状态数乘以转移代价。第三步改成递推填表。把记忆化递归转成自底向上的循环按依赖顺序填表。这一步的意义是消除递归开销、方便做空间优化。答题时写递推版本更规范老师也更认可。这三步看着简单但它是应对“从没见过的新 DP 题”的最强武器。考场上遇到陌生题不要慌着找记忆里类似的题直接按这三步硬推八成能推出正确方程。4.2 高频 DP 题清单与状态方程下面这张表是我整理的期末高频 DP 题覆盖八成以上的设计题场景题目状态定义转移方程核心复杂度0-1 背包f[i][c] 前 i 件容量 c 最大价值max(不选, 选)O(nC)完全背包同上但物品无限选的方向改为 j 递增O(nC)最长公共子序列 LCSf[i][j] 前 i、前 j 的 LCS 长度相等则 1否则取 maxO(nm)最长递增子序列 LISf[i] 以 i 结尾的 LIS 长度max(f[j])1, a[j]a[i]O(n²)/O(n log n)编辑距离f[i][j] 前 i、前 j 的最小操作数增删改三选一O(nm)矩阵连乘f[i][j] 区间最小乘法次数枚举断点 kO(n³)最大子段和f[i] 以 i 结尾的最大和max(a[i], f[i−1]a[i])O(n)钢条切割f[n] 长度 n 的最大收益max(p[i]f[n−i])O(n²)最长回文子序列同 LCS 思路逆序匹配相等 2否则取 maxO(n²)这张表的价值在于它把“状态定义”和“转移方向”一起给你了很多同学方程写对了却因为循环方向错误0-1 背包里正序还是逆序而丢分。记住一个口诀0-1 背包逆序完全背包正序。逆序是为了保证每件物品只用一次正序则允许重复使用。这个细节几乎每年都有人栽。区间型 DP矩阵连乘、石子合并的套路是枚举区间长度再枚举断点。外层循环是区间长度 len 从 2 到 n中层是起点 i内层是断点 k。这个三层循环的顺序千万不能乱因为大区间依赖小区间的结果必须按长度递增填表否则取到的是还没算的值。4.3 空间优化的思路与边界DP 的空间优化是进阶技巧也是区分度所在。核心思想是观察转移只依赖哪些层如果 f[i] 只依赖 f[i−1]就能把二维压成一维如果依赖 f[i−1] 和 f[i]就用两个变量或两行滚动。0-1 背包的经典压缩把 f[i][c] 压成 f[c]然后在容量维度逆序遍历。为什么逆序因为逆序保证你用到的是“上一轮未更新的 f[c−w]”如果正序就会用到本轮已经选过的 f[c−w]等于允许重复选那就变成完全背包了。这是空间优化里最容易搞错的方向问题。LIS 的 O(n log n) 优化是个亮点用一个数组 dd[k] 表示长度为 k 的递增子序列的最小结尾元素。遍历每个元素时二分查找它在 d 中的位置替换。这个技巧考得不多但很出彩写出来能加分。提示空间优化不是必须的考场上如果时间紧、状态没把握老老实实写二维版本正确性优先。宁可多花 O(n) 空间也不要为了炫技压错维度导致全盘皆输。5. 贪心与回溯两条相反的思路贪心和回溯是这门的“两极”。贪心一条路走到黑、不回头的乐观派回溯是每条路都试探、走不通就回退的谨慎派。它们经常被放在一起考就是让你判断“这道题该乐观还是该谨慎”。5.1 贪心正确性证明的两个套路贪心的可怕之处在于它能求出一个解但这个解不一定是最优的。所以凡是问“能否用贪心”你必须先证明贪心选择性质。期末考最常用的两个证明套路是交换论证法和数学归纳。交换论证法是证明贪心的标准武器。思路是假设存在一个最优解如果它的第一步选择和贪心选择不同那么我们通过交换把它的第一步换成贪心选择证明解不会变差。由于每一步都能交换最终这个最优解就变成了贪心解从而贪心解就是最优解。以活动安排问题为例贪心策略是每次选结束时间最早的活动。证明时假设最优解的第一个活动是 a贪心的第一个是 bb 结束更早。因为 b 结束更早把 a 换成 b 后剩下的活动时间不会更紧所以解不会变差。经典题目像哈夫曼编码、最小生成树Prim、Kruskal、单源最短路径Dijkstra都靠这套证明。什么题不能用贪心也是必考。0-1 背包就是经典反例按单位价值贪心会出错。举个具体例子背包容量 10物品 A 重 6 价值 6单位价值 1物品 B、C 各重 5 价值 5单位价值也是 1。贪心先取 A剩 4 装不下 B 或 C总价值 6但最优是取 B、C总价值 10。所以 0-1 背包必须 DP。而分数背包物品可切分就能用贪心因为可以切一部分凑容量没有“装不下就浪费”的问题。这个对比是高频考点务必记牢。5.2 回溯法的框架与剪枝技巧回溯法的本质是在解空间树上做深度优先搜索。它的通用框架非常固定def backtrack(路径, 选择列表): if 满足结束条件: 记录结果 return for 选择 in 选择列表: if not 可行(选择): # 剪枝 continue 做选择 backtrack(路径, 选择列表) 撤销选择 # 关键回溯这个框架的核心是“做选择”和“撤销选择”成对出现保证进入下一层时状态干净。很多同学写回溯忘了撤销导致答案错乱是经典失误。回溯的效率完全靠剪枝。剪枝分两类可行性剪枝当前部分解已经违反约束直接剪和限界剪枝当前部分解已经不可能优于已知最优解直接剪。N 皇后问题里剪枝条件是“同列、同对角线不能有皇后”子集和问题里如果当前和已经超过目标就剪枝。写了剪枝的回溯和没写的性能可能差好几个数量级考试里明确要求剪枝的题一定要写上不然即使答案对也被扣分。经典回溯题清单N 皇后、子集和、图着色、哈密顿回路、迷宫路径、数独。它们的共同点是解空间树是中序或排列树元素不能重复使用所以需要 visited 标记。这里有个易混点遍历所有排列用排列树遍历所有子集用子集树。排列树每个节点有 n−k 个分支子集树每个节点有“选/不选”两个分支复杂度分别是 O(n!) 和 O(2^n)。5.3 分支限界与回溯的区别分支限界经常和回溯一起考但两者的搜索方式不同。回溯是深度优先栈/递归分支限界是广度优先或优先队列队列/堆。回溯用“剪枝”砍掉不可能的分支分支限界用“限界”估算每个节点的上界或下界优先扩展最有希望的节点。最大团问题、旅行商问题TSP、0-1 背包的优化版本常用分支限界。考试里如果题目要求“用分支限界法”你要写出限界函数bound function这个函数的松紧程度直接决定算法效率。限界函数越紧剪枝越狠但也越难设计这中间的权衡是设计题可以发挥的地方。6. 图算法与 NP 完全性两大理论板块图算法和 NP 理论是期末里两个比较“独立”的板块。图算法偏实现和计算NP 理论偏概念和形式化推理。它们的分值通常加起来占到三四成但复习方式完全不同。6.1 图算法的必考三件套最小生成树考 Prim 和 Kruskal 两个算法。Prim 从点出发适合稠密图用邻接矩阵加数组维护最小权值复杂度 O(n²)Kruskal 从边出发适合稀疏图用并查集加边排序复杂度 O(e log e)。两者都是贪心证明都用切割性质。选择题常问“稠密图用哪个”答案是 Prim。单源最短路径的核心是 Dijkstra、Bellman-Ford、Floyd 三兄弟。Dijkstra 是贪心不能处理负权边用优先队列优化后 O((ne) log n)Bellman-Ford 是动态规划能处理负权边、能检测负环复杂度 O(n·e)Floyd 是全源最短路三重循环枚举中转点O(n³)。这里有个经典易错点Floyd 的中转点 k 必须是最外层循环因为它是按“允许经过前 k 个点”的阶段划分的写错循环顺序结果会错。网络流考最大流最小割定理。Ford-Fulkerson 是基础框架Edmonds-Karp 用 BFS 找增广路保证 O(n·e²)Dinic 用分层图更快。考试里通常考“求最大流并找出最小割”你只要会画残量网络、反复找增广路就行不需要写复杂代码。6.2 NP 完全性证明的归约套路NP 理论是很多人头疼的部分但它的考法极其固定。核心概念必须区分清楚P 是多项式时间可解的问题NP 是多项式时间可验证的问题NPC 是 NP 中最难的一类NPH 是至少和 NPC 一样难的所有问题。注意 P ⊆ NP 是确定的但 P 是否等于 NP 至今未知。证明一个问题是 NPC 分两步先证明它属于 NP给出一个多项式时间的验证算法再选一个已知 NPC 问题归约到它比如从 3-SAT 或顶点覆盖归约。归约的意思是把已知问题的任意实例在多项式时间内转换成新问题的实例使得新问题有解当且仅当原问题有解。常见的归约链条是SAT → 3-SAT → 团问题 / 顶点覆盖 / 哈密顿回路 → TSP。考试里通常让你做一步简单归约比如“证明顶点覆盖是 NPC”你只需要说清楚归约怎么构造、证明对应关系、说明多项式时间即可。注意判定问题时别把 P 和 NP 说反了。很多人直觉觉得 NP 是“非多项式”其实 NP 是“非确定性多项式时间可解”也就是多项式时间可验证。这个概念题几乎每年都出。6.3 近似算法与下界的思想NP 难问题无法在多项式时间内求最优解于是有了近似算法。评价近似算法用近似比算法解不超过最优解的 ρ 倍。比如顶点覆盖有 2-近似算法TSP 在满足三角不等式时有 1.5-近似。期末里如果考到“设计一个近似算法并分析近似比”写出贪心策略和比值分析就够了。另一类常考的是下界证明主要用于排序问题。基于比较的排序下界是 Ω(n log n)证明用的是决策树n 个元素的排列有 n! 种决策树至少要有 n! 个叶子二叉树的深度至少是 log(n!) Θ(n log n)。这个证明每年必考务必背下来。7. 编程题实战模板与手写细节编程题是很多人最紧张的部分尤其是“算法设计与分析期末编程题”这个热搜词说明大家普遍在这栽跟头。我的建议是不要指望临场从零构思而是提前准备一套能套用的模板考场上根据题意微调。7.1 必背代码模板归并排序与合并是编程题的基础很多题求逆序对、稳定性排序都基于它def merge_sort(a, l, r): if l r: return mid (l r) // 2 merge_sort(a, l, mid) merge_sort(a, mid 1, r) i, j, tmp l, mid 1, [] while i mid and j r: if a[i] a[j]: # 取等号保证稳定 tmp.append(a[i]); i 1 else: tmp.append(a[j]); j 1 tmp.extend(a[i:mid1]) tmp.extend(a[j:r1]) a[l:r1] tmp求逆序对只需在a[i] a[j]时累加mid - i 1这是经典变形。二分查找的三个版本必须分清找目标值、找左边界、找右边界。考场上最常见的错误是死循环根源是while l r还是while l r、mid要不要加一没搞清。记忆口诀找左边界用mid (lr)//2找右边界用mid (lr1)//2这样能避免死循环。0-1 背包的一维写法def knapsack(w, v, C): n len(w) f [0] * (C 1) for i in range(n): for c in range(C, w[i] - 1, -1): # 逆序 f[c] max(f[c], f[c - w[i]] v[i]) return f[C]回溯的 N 皇后框架建议背到能默写因为它的“做选择—递归—撤销”结构是通用套路。7.2 手写代码的考场细节机试和手写代码的评分点不完全一样。手写代码时老师看的是思路和边界不是能不能编译通过。所以手写时一定要写清楚函数签名和参数含义标注关键步骤的注释处理边界空数组、单个元素、越界写出复杂度。如果是机试除了正确性还要注意输入输出格式。很多同学算法对了却因为没按题目格式读入多组数据而全盘皆输。建议机试前把输入模板练熟比如while True: try: ... except EOFError: break处理不确定组数、n, m map(int, input().split())处理一行多值。我的踩坑记录有次机试题目是“多组测试数据直到文件结束”我按单组写的结果第三个测试点就挂了。从那以后我养成了习惯——先看输入描述里的“多组”“直到 EOF”这些关键词再决定读入方式。8. 常见问题与排查速查最后这部分是我认为整篇最有价值的。下面这些坑要么是我自己踩过的要么是看过别人踩的整理成速查表方便你考前扫一遍。现象可能原因排查方向DP 答案偏小循环方向反了0-1 背包写成正序检查容量维度是否逆序DP 答案偏大状态重复计算或没取 max/min检查转移是否漏掉“不选”分支递归爆栈递归深度太大改迭代或加尾递归/增大栈回溯答案缺失忘了撤销选择检查“做选择”和“撤销”是否成对快排退化 O(n²)主元选得不好用随机主元或三数取中Floyd 结果错中转点循环位置不对k 必须是最外层二分死循环mid 计算方式和边界不匹配对照左右边界模板贪心结果非最优该用 DP 却用了贪心找反例验证贪心选择性质关于复习时间安排我的经验是别平均分配。考前一周用两天刷复杂度分析和分治两天主攻动态规划一天搞贪心和回溯一天扫图算法和 NP最后一天专门背模板和看错题。这样安排的原因是前两块确定性强、见效快DP 分值最高后面几块靠模板能保底。还有一点想提醒错题比新题重要得多。期末复习阶段最忌讳疯狂刷新题却从不回头看。我建议准备一个错题本只记“我为什么错”这一句话考前翻一遍能避免的失分比多刷十道题都多。另外考试时遇到完全没思路的设计题别空着。写出你能想到的暴力解法、分析它的复杂度、说明瓶颈在哪、给出优化方向这样即使没写出最优解过程分也能拿不少。老师们普遍对“有分析过程的部分解”给分不低而对空白卷只能给零分。这个策略我在好几门算法课上用过屡试不爽。至于证明题如果实在推不出来至少把定义和思路框架写出来。比如证明贪心先写“我尝试用交换论证法”再写“假设存在最优解使得第一个选择不同于贪心”把开头这几句写上后面哪怕不完整老师也知道你懂套路通常会给步骤分。空着是绝对不划算的。