《算法设计技巧与分析》这本书在很多高校的算法课里都是指定教材也是我当年复习时最头疼的一门课。题目倒不是真的做不完而是做完了不知道自己做得对不对这件事特别折磨人——教材没有官方答案网上流出来的答案分散在各类博客和个人仓库里有的题号跟中文版对不上有的直接是错的还有的根本是从其他教材里搬过来的答案张冠李戴。我后来花了很长时间把整本书的习题系统过了一遍把能找到的答案逐一比对、修正、重写顺带把自己的解题思路完整记录了下来。这篇内容就是基于那次整理的总结把这本书的题目类型、答题套路、常见错误和整理答案时踩过的坑做一个梳理给正在学这门课或者准备考试的人一条相对省力的路。1. 这本教材的习题到底在考什么先建立自己的知识地图很多同学翻开这本书的习题册第一反应是题太多、太杂、看不懂在考什么于是开始一道一道硬刷。刷到第三章就放弃算了。我的经验是不动手之前先花半天把整本书过一遍把题目按类型归类效率会翻倍。1.1 教材目录背后的三条主线《算法设计技巧与分析》的章节看似零散实际上就三条主线。第一条是设计技术线分治法、动态规划、贪心算法、回溯法、分支限界法。这一条线是全书的主体也是课后习题最集中的地方。习题的典型问法是用分治策略设计一个算法解决某问题或者给出该问题的动态规划递推关系式。第二条是分析方法线渐近记号、递推关系求解、复杂度分析、正确性证明。这部分题目看起来是数学题实际上是后面所有算法题的基础。递推关系求解几乎出现在每一章的复杂度分析里。第三条是问题复杂度理论线包括图算法、NP完全性、近似算法。这部分题目偏理解风格跟前面完全不同。1.2 习题的三种出题形态我把课后题归纳成三类方便分配复习精力计算题解递推式、算渐近复杂度、画动态规划表。这类题最机械但最容易丢分因为细节多。证明题证明算法正确性、证明贪心选择性质、证明某个问题是NP完全的。这类题靠套路和积累。设计题针对问题设计算法往往要求给出伪代码、分析复杂度。这类题最能拉开差距也是答案整理里最容易出问题的地方。我整理答案时的原则是计算题必须手推一遍证明题先不看结论自己尝试设计题则必须把伪代码写到能跑通的程度——后面你会发现很多网上答案在伪代码里是有逻辑漏洞的。2. 递推关系求解主定理之外的保底手段与常见翻车点递推关系是这本书几乎所有复杂度分析的核心。很多习题的第一问就是求以下递推式的渐近界。这部分看着简单坑却特别多。2.1 三种求解方法的选用逻辑递推求解最常见的有三种方法展开法迭代法、代入法、主定理法。它们的定位完全不同不能一味全靠主定理。展开法是最保底的手段适用于任何递推式。核心思路是把递推反复展开观察规律得到一个级数求和的形式然后再求和。比如最经典的T(n) 2T(n/2) n展开T(n) 2[2T(n/4) n/2] n 4T(n/4) 2n继续展开到 T(1)每一层都多一个 n一共 log₂n 层所以 T(n) Θ(n log n)。这个推导过程本身也是考试时的采分点直接写主定理结论有时候只能得结论分。代入法更像猜谜加归纳先猜一个渐近界再用数学归纳法证明。这个方法在证明题里非常有用比如证明 T(n) O(n²)你得假设 T(n/2) ≤ c(n/2)²然后代入原递推式验证存在某个常数 c 使得不等式成立。要注意的是归纳证明时 c 的取值必须够大而且不能依赖 n 的系数产生矛盾这是一个常见的细节点。主定理法适用于形如 T(n) aT(n/b) f(n) 的递推式直接对比 f(n) 和 n^(log_b a) 的大小关系。书上的三种情况本质上是在比较分治部分的代价和合并部分的代价谁占主导。2.2 主定理的边界条件与翻车场景我整理了大量网上的答案发现主定理这里有三种特别容易翻车的情况第一种是忽略了取整符号。递推式里如果写的是 T(n) 2T(⌊n/2⌋) n严格来说主定理需要特殊处理。不过考试通常默认取整不影响渐近结果但如果题目专门强调取整答案里必须提一句取整对渐近阶无影响。第二种是f(n)不在多项式范围内。主定理要求 f(n) 与 n^(log_b a) 之间的比较满足多项式意义上的差距。如果 f(n) n/log n它小于 n^(log_b a) 但差距不是多项式级别的这时候主定理的三种情况都不能直接套用。答案里如果只写由主定理得必然丢分。第三种是我见过最多的T(n) 2T(n/2) n log n 这类递推式。主定理可以套用情况二扩展版结论是 T(n) Θ(n log² n)。很多人记不住这个扩展结论会误以为答案是 Θ(n log n)然后整道题全错。整理答案时我建议大家把主定理的扩展形式单独抄出来如果 f(n) Θ(n^(log_b a) · log^k n)则 T(n) Θ(n^(log_b a) · log^(k1) n)。k ≥ 0 时成立。2.3 一道完整的递推题答案示范我拿整理时遇到的一道题做示范。求 T(n) 3T(n/4) n log n 的渐近界。这里 a 3b 4所以 n^(log_4 3) ≈ n^0.793。f(n) n log n。因为 n log n 比 n^0.793 增长更快而且存在某个 ε 0 使 n log n Ω(n^(0.793ε))正则条件 a·f(n/b) ≤ c·f(n) 也满足所以属于主定理第三种情况。答案要写完整T(n) Θ(n log n)。很多人只写结论不验证正则条件严格来说是不完整的。我整理答案时凡是涉及主定理第三种的证明都会补上正则条件的验证这在考试里是加分项。3. 分治与减治题目的题眼跨中点的合并步骤决定成败分治法章节的习题套路非常固定分解、递归、合并但真正拉开差距的是合并步骤怎么设计。网上很多答案把分解和递归写得很详细一到合并就含糊带过这恰恰是分治题最核心的得分点。3.1 最大子数组问题为什么必须单独考虑跨中点情况这道题要求在一个数组中找到和最大的连续子数组。朴素解法是 O(n²)分治解法要求 O(n log n)。分治的思路是把数组从中间分成左右两半最大子数组要么完全在左半边要么完全在右半边要么跨越中点。前两种递归解决第三种必须单独计算——从中间向两边扩展找从中间向左的最大后缀和以及从中间向右的最大前缀和最后相加。我在整理答案时特别标注了一个注意点合并步骤里向左扩展和向右扩展是独立计算的不能混在一起。有些答案写成了从中间向左找最大和再继续向左找次大和这就不是跨中点的子数组了。还有的答案在计算跨中点最大和时忘了比较它与左右子数组最大值的大小这也是个容易漏掉的细节。3.2 第k小元素与划分的运气问题第k小元素的分治解法Quickselect在书上的写法是用一个划分算法把数组分成两部分然后根据 k 与划分点的位置关系决定递归进入哪一侧。这道题的答案容易在划分点选择上出现问题。最朴素的答案是每次选第一个元素当主元最坏情况下 O(n²)。更高级的答案是中位数的中位数选主元保证最坏 O(n)。整理答案时我发现很多网上版本两个方案混着写一会儿说选第一个一会儿说保证线性逻辑不可自洽。复现这道题答案时我建议把问题拆成三种场景只需要写出平均 O(n) 算法随机选主元或选第一个分析期望复杂度。要求最坏 O(n)必须写中位数的中位数选主元且分析划分后的分组数量。只要求比较复杂度上界直接引用结论不展开细节。3.3 最近点对问题合并步骤是整道题的灵魂最近点对问题的分治解法合并步骤应该是全书中最精巧的合并之一。左右两边递归求完各自的最小距离 δ 之后合并阶段只需要考虑距分割线 δ 范围内的点而且这个范围内的点最多只需要和按 y 坐标排序后相邻的常数个点比较距离。这个常数个点是怎么来的是证明的关键。整理这道题的答案时我踩过一个坑网上有一版答案写的是将距分割线 δ 范围内的点按 y 坐标排序后每个点只需检查后面的 7 个点。这个 7 是理论上界但很多实现里检查 4 个或 6 个也能跑对。我不建议在答案里写死一个具体数字除非题目明确要求。更稳妥的做法是写成只需检查常数个点然后说明常数来自几何性质或者按教材指定的版本写。4. 动态规划答案的完整链路状态定义、转移方程与回溯构造如果说分治的题眼是合并那动态规划的题眼就是状态定义。同一个题状态定义得好不好直接决定答案的篇幅和可读性。我整理动态规划题答案时都会按一个固定模板走定义子问题 → 写递推关系 → 确定计算顺序和边界条件 → 构造最优解。四步缺一不可。4.1 最长公共子序列LCS的填表与回溯LCS 是几乎所有教材都有的例题但我在网上看到的答案参差不齐。完整的答案应该包含状态定义设 c[i][j] 表示序列 X[1..i] 与 Y[1..j] 的 LCS 长度。递推关系若 X[i] Y[j]则 c[i][j] c[i-1][j-1] 1若 X[i] ≠ Y[j]则 c[i][j] max(c[i-1][j], c[i][j-1])边界条件c[i][0] 0c[0][j] 0。只写到这一步只能拿一半分。另一半在构造最优解从 c[m][n] 开始回溯当 X[i] Y[j] 时记录该字符并斜向移动否则向值更大的方向移动。如果两个方向值相等任选一个即可——这说明 LCS 不唯一。网上答案最常见的问题是在递推关系里漏了X[i] Y[j] 时取斜对角 1这一个分支整个表的箭头方向就全乱了。我整理这道题时画了一张 c 表把每个格子的方向箭头标注出来复习时一眼就能看到回溯路径这个方法比空背公式扎实得多。4.2 矩阵链乘法重叠子问题的最直观例证矩阵链乘法习题的标准答案是括号化问题。朴素枚举所有括号化方案的数量是卡特兰数指数级动态规划把子问题定义为 m[i][j]表示 A_i A_{i1} ... A_j 的最小标量乘法次数。递推关系是m[i][j] min{ m[i][k] m[k1][j] p_{i-1} p_k p_j }其中 i ≤ k j答案里最容易错的是 p 数组的下标。p 数组存的是矩阵维度A_i 是 p_{i-1} × p_i所以合并两个子链时的乘法代价是 p_{i-1} × p_k × p_j。很多答案这里下标写错一位结果就是整道题全错。整理时我习惯在答案开头先把 p 数组列出来再进入递推这样下标就再也不会混。计算顺序也很关键按链长从小到大计算对角线方向的格子而不是按矩阵编号从左到右算。书里有一张经典的三角表左上到右下的对角线对应链长递增。答案里如果没有说明这个计算顺序考试时手算很容易算错或算重复。4.3 动态规划与分治的本质差别这部分教材里讲得不算多但习题里几乎必然会问或者暗含动态规划和分治的区别。我的理解是两者都是把大问题拆成小问题但分治的子问题是相互独立的动态规划的子问题是重叠的。重叠子问题是动态规划能优化复杂度的根本原因——把重复计算的子问题结果存起来。这个点写进答案的分析部分一下子就能把答案的档次提上去。我在整理很多动态规划题的答案时都会在最后加一段为什么这个递推关系适合用动态规划而不是分治考试时老师看到这种分析通常都会给高分。5. 贪心算法构造解只是入门正确性证明才是拿分点贪心算法的习题特别有意思答案的构造部分往往几句话就写完了比如每次选结束时间最早的活动然后呢没了。不少同学给出的答案就停在构造这里觉得题目已经做完了。但在考试里这道题的分值大头其实是正确性证明——你要证明这个贪心策略能得到全局最优解。5.1 活动选择问题的两种证明套路活动选择问题给一堆区间选尽量多的互不重叠的活动。贪心策略是按结束时间排序依次选结束时间最早且不与已选活动冲突的活动。答案的构造部分只需要一句话。证明部分就要花篇幅了。常见做法是交换论证假设最优解中第一个活动不是结束时间最早的活动 a把最优解里的第一个活动换成 a得到的解不会更差因为 a 的结束时间不晚于原活动剩余区间只会更多。重复这个换入换出的过程贪心解就能变成某个最优解所以贪心解也是最优的。另一种情况是用归纳法证明贪心选择 子问题独立性。我整理答案时发现教材习题里如果题目问证明该算法正确用交换论证通常最通用如果题目问证明贪心选择性质则需要更正式地说明为什么每次贪心选择都不会排除最优解。5.2 哈夫曼编码最优性证明的完整链条哈夫曼编码的贪心策略是每次合并权值最小的两棵树。这个策略的正确性证明比活动选择麻烦需要两个引理引理一存在某个最优前缀码其中两个权值最小的字符对应的编码长度最长且互为兄弟。引理二把这两个字符合并成新字符后新问题的最优解可以对应原问题的最优解。第二个引理是归纳的桥梁。网上很多答案只写引理一不写引理二导致证明链断裂——只证明了贪心第一步是安全的没证明合并之后递归执行仍然安全。我在整理答案时把两步分开写中间明确标注这是归纳假设证明就显得完整得多。5.3 贪心与动态规划的边界案例整理贪心习题时最难判断的是这道题到底能不能用贪心。0-1背包不能贪心部分背包能贪心找零钱问题在某些币制下能贪心某些币制下不能。我在这个部分的答案里做了一个对比表方便复习定位问题同类动态规划思路贪心是否成立原因部分背包按单位价值排序成立物品可分割局部最优即全局最优0-1背包动态规划可行不成立选/不选会改变剩余空间贪心会错过组合解活动选择区间动态规划也可以解成立活动区间可替换最早结束不会劣化哈夫曼编码动态规划也可构造最优树成立合并最小权值可用交换论证证明这个表整理完我自己复习的时候明显少走了很多弯路。建议你也照着自己的教材做一份类似对照表效果比死记题目好得多。6. 图算法与NP完全性属于背了就有分与理解才有分的混合区图算法和 NP 完全性部分风格跟前面的分治、动态规划很不一样。前面是你想得到就是会做想不到就是不会做图算法部分很多题是记住算法流程就能拿分NP 完全性则是理解归约方向才有分。6.1 三张图算法表解决大部分计算题我在整理这部分答案时把所有图算法的关键信息汇总成了三张表。第一张是最短路径算法适用图核心思想时间复杂度Dijkstra非负权边贪心每次选当前最近未访问节点O((VE) log V) 用堆Bellman-Ford允许负权边松弛所有边 V-1 轮O(VE)Floyd-Warshall任意图含负权边动态规划中间点枚举O(V³)第二张是最小生成树算法适用场景核心思想时间复杂度Kruskal稀疏图按边权从小到大并查集判环O(E log E)Prim稠密图维护最小割边集O(V²) 或 O(E log V)第三张是拓扑排序、强连通分量等基础问题。表的额外价值在于考试时看到给出某算法运行过程这种题按表里的流程走一遍就不会漏步骤。整理答案时每个算法我都配合了一个小例子跑一遍比如 Dijkstra 的逐步松弛过程这比只贴算法伪代码直观得多。6.2 NP完全性的核心归约方向不能搞反教科书在 NP 完全性章节通常会给出一个基本事实SAT 是 NP 完全的Cook-Levin 定理然后通过多项式时间归约证明其他问题也是 NP 完全的。这部分习题常见有两种一是概念问答题问 P、NP、NP完全、NP难的关系二是证明题给你一个新问题让你证明它是 NP 完全的。概念题答案基本是固定的我整理时最注意的是那幅经典的包含关系图P ⊆ NPNP 完全问题是 NP 中最难的一类NP 难问题不要求属于 NP。这些结论背下来就能拿分。证明题的套路是固定两步证明该问题属于 NP给出一个证书并说明可以在多项式时间内验证。证明该问题是 NP 难的选一个已知的 NP 完全问题 A构造一个从 A 到目标问题 B 的多项式时间归约。最容易翻车的点是归约方向。很多同学的直觉是把目标问题归约到已知问题这是反的。正确的是从已知的 NPC 问题出发构造它的一个实例转换成目标问题实例从而把目标问题包含整个 NPC 类的难度。这个方向如果记反整道证明题一分都拿不到。我在答案整理里用粗体字标了这句话三遍就是想让自己考前不会忘。6.3 摊还分析在这本书里的角色摊还分析严格来说属于分析方法但在图算法和后续章节用得最多。书里通常讲三种方法聚合分析、核算法、势能法。习题一般是证明某数据结构一组操作的摊还复杂度是 O(1)。整理这部分答案时我倾向于用势能法作为首选因为它的套路最固定设计一个势函数 Φ(D_i)让第 i 次操作的摊还代价等于实际代价加上势能变化。只要势函数满足 Φ(D_i) ≥ 0 且 Φ(D_0) 0总摊还代价就是总实际代价的上界。三种方法对比下来聚合分析需要想象力核算法需要给每种操作设计存款势能法相对更机械化。7. 整理答案时踩过的坑和验证答案的方法最后这部分是我最想分享的实操经验。整理整本书答案的过程中我遇到了不少问题有些问题浪费了我大量时间写出来给后来人避坑。7.1 网传答案的错误类型网上的《算法设计技巧与分析》答案整理常见问题有这么几类题号错乱中文版和英文版的章节内容有差异很多答案是照着英文版第六题写的但中文版对应的是第八题。对答案时发现我按你的思路做但跟题目对不上先检查是不是题号错位。伪代码运行不了有些答案的伪代码用了不存在的语言特性或者在数组索引上出现了越界。最典型的是动态规划里数组下标从 1 还是从 0 开始的问题——答案里有时混用。偷懒省略关键步骤证明题只写由归纳法可得设计题只写仿照课本方法。这类答案参考价值很低。看到一份答案时我会先看它有没有覆盖以上说的题眼部分分治题的合并步骤、动态规划题的边界条件和回溯、贪心题的证明过程。如果这些都没有果断放弃这份答案。7.2 我自己验证答案是否正确的两个手段第一个手段是写代码跑小规模数据。对于设计题和计算题我会把伪代码快速转成 Python 或 C用随机小数据跟暴力解法对拍。比如最大子数组、LCS、矩阵链乘法这些问题暴力解法几行就能写完随机测几百组数据答案是否正确一目了然。实测下来这个方法至少帮我抓出了三处网上答案的错误。第二个手段是用边界条件自查。每个动态规划答案把 n0、n1 代入递推式看看边界条件是否成立每个分治答案把数组长度设为 1 或 2 走一遍流程看递归是否正常终止。很多错误的答案在边界条件上会露出破绽。7.3 不同基础的复习路线建议如果你现在才开始接触这本书我的建议是按这个顺序来先把第二章递推关系彻底吃透这一章过不了后面每个算法的复杂度分析都看不懂。然后分治和动态规划并重这两章是设计题的高频出题区。贪心算法重点看证明套路不用刷太多题。图算法把表格背熟、经典流程手推几遍即可。NP 完全性只要记住归约方向会做教材例题级别的证明题就够。如果你已经学完一遍只差考前冲刺那就直接做每章最后几道综合题并且严格按照写出状态定义、递推式、伪代码、复杂度分析四步来练习。我整理答案时发现四步齐全的答案即使结论有小瑕疵老师给的分数也远高于那种步骤不全、但答案正确的压缩版。最后说一个我个人的体会整理答案最忌讳的是看答案。看十遍别人的解题过程不如自己动手推一遍。我当时把每一章的重点题都亲手写过一遍伪代码那些出错的点、卡壳的地方事后都成了复习时的高价值标记——因为那是你自己的薄弱点不是别人的。这份工作虽然耗时但做完之后我对算法的理解比以前翻了几倍都不止。