算法概论课后作业通关指南：从分治到动态规划的系统拆解与实战复盘

算法概论这门课的课后作业在一个普通学期里看起来只占成绩的一小部分但真正静下心把每一道题做完之后会发现它就是整门课的浓缩版地图。当时我陪读的A同学拿到第一份作业前面几道题还能轻松应付越往后越发现自己对递归、分治的理解只是“听过”而不是“会用”。这篇内容不打算抄讲义也不罗列答案而是从一个作业进阶者的视角聊聊这份作业到底在考什么、怎么拆题、怎么绕开那些让无数人卡住的坑。如果你正在修这门课或者只是想系统补一遍算法基础这篇应该能帮你省下不少熬夜时间。1. 这门课的课后作业到底在考什么1.1 从题目分布反推课程主线一份典型的算法概论课后作业看起来只是几道编程题的集合但题目顺序其实暗含了课程的推进逻辑。通常前面几题围绕复杂度分析、递归树、主定理展开要求你计算某个递推式的时间复杂度或者手写一个递归函数中间部分开始进入分治、排序、动态规划、贪心最后总有一两道综合性题目把图论、搜索、数据结构组合在一起。这不是老师随意排的而是在用作业告诉你算法不是孤立知识点的拼盘而是一条从“分析复杂度”到“设计算法”再到“代码落地”的完整链路。我见过不少同学拿到作业后直接从最后一道难题开始做结果卡了一晚上前面送分题却空着。正确的做法是先扫一遍全部题目按知识点分类再排一个从易到难的顺序。因为很多综合题里的子问题其实就藏在前面那些基础题里。比如动态规划的滚动数组会先在一道背包题里出现然后在最后那道区间调度题里升级成二分加动规的组合。1.2 送分题、进阶题、综合题的三层结构课后作业的每一题都可以粗略分成三层。第一层是“送分题”用来确认你听懂了基本概念比如让你比较几个排序算法在最好、最坏情况下的复杂度或者补全一段二分查找的边界判断。这种题不能丢分它考察的是细心而不是智商。第二层是“进阶题”需要你独立完成一个小型算法设计典型代表是“用分治求逆序对数量”或者“实现带滚动数组的最长公共子序列”。这类题开始有区分度很多人能说出算法名字但写不出完整代码或者在边界条件上栽跟头。第三层是“综合题”通常融合了排序、二分、贪心、动态规划中的两个以上知识点需要你自己抽象模型。我在实际辅导中观察到前两层刷得快的同学往往不是代码写得快而是对数据结构和复杂度的敏感度高。综合题才是真正拉开差距的地方。1.3 分数之外作业真正的训练目标如果只把作业当成拿分的任务那就浪费了这门课最宝贵的东西。课后作业和期末考试的差别在于作业允许你查资料、反复调试、跑实验数据这实际上是一次完整的算法工程训练。你需要读懂题意设计数据结构估算复杂度写出边界处理完备的代码还要自己构造测试用例去验证。这一套流程和日后在真实系统里优化一段查询逻辑、设计一个调度策略的过程几乎一模一样。很多人在工作后遇到性能问题第一反应是加服务器而不是想着能不能用更好的算法就是因为当年作业只求跑通没有养成“先分析复杂度、再动手编码”的习惯。课后作业真正要训练的是这种在任何代码还没开始写之前就已经在心里画出解法框架的能力。2. 作业里的核心算法逐个拆给你看2.1 分治与递归凭什么能把时间复杂度降下来分治几乎是算法概论作业里第一个真正需要“理解”而非“背诵”的算法。它的核心只有一句话把大问题拆成若干个规模更小的子问题分别解决再合并结果。听起来简单但为什么归并排序是 O(n log n) 而冒泡排序是 O(n²)很多人并没有真正想透。关键在于每一层递归里所有子问题的总工作量是多少。用主定理 T(n) aT(n/b) f(n) 来算如果合并的代价 f(n) 小于 n^log_b(a) 的数量级总时间就由叶节点数量主导如果合并代价更大总时间就由根节点主导。这个公式不需要背但需要会用来估算你设计的递归算法够不够快。作业里最常见的分治题是“求逆序对数量”。暴力法是两层循环O(n²) 在 n 到十万级别时直接超时。用归并排序的分治思路在合并两个有序子数组时如果右侧子数组的某个元素比左侧小那么左侧剩余的所有元素都构成逆序对这样一次合并就能统计出跨左右两侧的逆序对数量总复杂度降到 O(n log n)。这类题的难点不在于“归并排序模板”而在于合并时统计逻辑的准确性和递归出口的处理。我的建议是不要把分治实现得过于抽象先用小数组手跑一遍合并过程把每个变量画出来再写代码。2.2 动态规划状态定义对了题目就做了一半动态规划在作业里的出现频率非常高也是让最多人头疼的部分。我见过一个很典型的场景某同学拿到一道“编辑距离”题知道要用动态规划但不知道 dp 数组怎么开状态转移方程对着答案也看不懂。其实动态规划的思考路径有固定套路先定义状态再写转移最后决定遍历顺序和初始化。以编辑距离为例dp[i][j] 表示把字符串 A 的前 i 个字符转换成 B 的前 j 个字符所需的最小操作数。转移时考虑最后一个字符如果相同直接看 dp[i-1][j-1]如果不同可以从插入、删除、替换三个动作里取最小值。初始化时一个空串变成非空串只能不断插入所以 dp[0][j] jdp[i][0] i。状态定义一旦对了代码其实就是把转移方程翻译成循环。作业里很多动态规划题难在状态定义不是一眼就能看出来的比如“最长上升子序列”可以用 O(n²) 的 dp也可以用贪心加二分的 O(n log n) 思路。后者严格来说不算纯动态规划但它把“状态”变成了“当前上升子序列的最小末尾值”理解这个转换会对算法设计有更深的认识。2.3 贪心算法靠直觉只能过样例证明才是关键贪心在课后作业里是最容易“骗自己”的一类题。很多题目看着明显能贪样例也能过但提交之后反复被测试数据打脸。原因很简单贪心算法成立需要两个条件——贪心选择性质和最优子结构。前者是说每一步的局部最优选择最终能导向全局最优后者是说整个问题的最优解包含子问题的最优解。作业里需要用文字或反证法证明这两点而不是只写一句“显然”。一个常见的贪心题是“区间调度”选最多不重叠区间。正确的贪心策略是按结束时间排序然后依次选择结束最早且与已选区间不冲突的区间。为什么不能按开始时间排序或者按区间长度排序因为提前结束能留给后续区间更多空间这个性质可以用交换论证证明。我在辅导 A 同学时让他试着构造一个反例去推翻“按开始时间排序”的策略他很快发现某个早开始但很长很长的区间会挡住后面一大片短区间。这个练习比背一百遍贪心定义都管用。作业里另一类贪心难题是哈夫曼编码它需要配合优先队列实现每次合并频率最小的两个节点。核心不是代码而是证明“频率最小的两个节点一定在最深层且互为兄弟”这个贪心选择性质。2.4 图论与搜索别一上来就写 SPFA图论题在课后作业里往往是压轴级别。DFS、BFS、拓扑排序、Dijkstra、最小生成树都有可能出现。很多同学拿到题先写记忆里的模板结果连图的存储方式都选错。这是我想重点提醒的看到题目先看数据范围。n 在几百以内可以用邻接矩阵简单直观n 到十万级别必须用邻接表否则矩阵本身就可能内存超限。判断算法也一样小数据量可以用 Floyd 求全源最短路代码只有三层循环大数据量就得上 Dijkstra 或堆优化版甚至在有负权边时要换 Bellman-Ford 或 SPFA。图论题最坑的不是算法本身而是对“图不连通”“存在环”“起点到终点不可达”这类边界条件的处理。有一次 A 同学做一道“拓扑排序输出字典序最小结果”的题逻辑没问题但没考虑存在多个连通分量的情况导致排序结果里漏掉一些节点。改法很简单初始把所有入度为零的节点全部放入优先队列而不是只放入入度为零且 id 最小的那一个。这个小小的修改恰恰体现了对算法初始化条件的理解深度。图论部分我的经验是把模板背熟很重要但更重要的是养成“先描述图的特征再选择算法”的习惯。3. 实操复盘一道典型作业题的完整解题过程3.1 题目描述与数据规模判断为了让你更直观地理解作业的完整流程我拿一道非常经典的作业题来复盘有 n 个任务每个任务有开始时间、结束时间和价值任务之间不能重叠问能获得的最大总价值是多少。这道题在作业里通常属于中上难度数据范围一般是 n ≤ 10^5开始和结束时间可能达到 10^9 的量级。看到这个范围第一反应应该排除“按时间轴做动态规划”因为时间轴太大也不能用 O(n²) 的枚举因为百万亿次操作在任何语言里都跑不动。这道题的正确模型是加权区间调度标准的解法是动态规划加二分查找。如果你之前没接触过也不用慌跟着下面的思路走。先把所有任务按结束时间从小到大排序然后定义一个数组 dp[i] 表示前 i 个任务所能获得的最大总价值。对于第 i 个任务我们可以选择做它也可以选择不做它。如果做就必须找到在它开始时间之前结束的最后一个任务记其编号为 p那么价值就是 dp[p] 该任务的价值如果不做价值就是 dp[i-1]。两者取最大值即可。3.2 从暴力思路到动态规划优化第一次接触这道题的同学很容易想到一个二维 DP用 f[t] 表示时间 t 之前能获得的最大价值然后遍历每个任务对开始和结束时间之间的所有时间点做转移。这个思路在小数据量下没问题但一旦时间范围达到 10^9数组都开不下。所以必须把思路从“以时间作为状态维度”转成“以任务排序后的下标作为状态维度”。这里最关键的一步是求 p。朴素做法是扫描 i-1 往前的每一个任务找到最后一个结束时间小于等于当前任务开始时间的任务这样每个任务都要 O(n)总复杂度 O(n²)。但注意因为任务已经按结束时间排序结束时间数组是单调递增的所以我们可以对每个任务用二分查找在 O(log n) 时间内找到 p。于是总复杂度变成排序 O(n log n) 加每个任务二分 O(n log n)加 DP 遍历 O(n)整体 O(n log n)。这个优化过程就是课后作业最想让你训练的东西不是记住一个题解而是当暴力方法遇到数据规模壁垒时如何利用排序和单调性来降复杂度。3.3 代码实现与复杂度验证下面是这道题的一个可运行实现使用 Python 写只是为了读起来清楚实际作业里用 C 也大同小异import bisect def solve(jobs): jobs.sort(keylambda x: x[1]) # 按结束时间排序 ends [job[1] for job in jobs] n len(jobs) dp [0] * (n 1) for i in range(1, n 1): start, end, value jobs[i - 1] # 找到结束时间 start 的最后一个任务下标p 表示前 p 个任务可用 p bisect.bisect_right(ends, start) # 选择做第 i 个任务价值 dp[p] value take dp[p] value not_take dp[i - 1] dp[i] max(take, not_take) return dp[n]写完代码不是终点。要用时间复杂度和额外空间来验证自己排序是 O(n log n)循环里每次 bisect 是 O(log n)所以总时间 O(n log n)空间上存 ends 和 dp 各 O(n)总空间 O(n)。这样的复杂度在 n10^5 时完全没问题。我曾经试过用扫描而不是二分来找 p结果在 n2万 的时候已经明显变慢n10万 时直接超时。所以复杂度估算不要只在脑子里过要真的跑数据看趋势。3.4 边界条件与对拍验证这道题容易出错的边界条件包括任务列表为空此时 dp[n] 返回 0存在开始时间和结束时间相等的情况这意味着一个任务的结束时间等于另一个任务的开始时间按照题意它们可以连续安排所以 bp 查找时要用 bisect_right 而不是 bisect_left否则你会漏掉刚好在开始时间点结束的任务所有任务都重叠那么每个任务的 p 都是 0dp 结果应该等于价值最大的那个任务的价值。这些细节不需要死记但必须通过测试样例自己验证。我强烈建议在提交作业前做一次随机对拍。写一个暴力求解函数用两层循环或按子集枚举的方式处理小数据再写一个生成随机任务列表的函数例如 n 取 1 到 20开始时间在 1 到 50 内随机结束时间在开始时间到 60 之间随机然后反复让暴力结果和优化解法跑同样的输入一旦发现输出不一致就手动把那一组数据缩小逐步定位问题。这个对拍习惯能帮你抓出 90% 以上的隐藏 bug比盯着代码看半天有效得多。4. 常见问题与排查技巧实录4.1 递归爆栈与超时的背后原因作业里的分治和搜索题很多人习惯用递归实现。递归代码看着舒服但有两个隐患一是函数调用栈的深度限制二是重复计算。前者在数据量大时直接导致运行时错误或崩溃。比如归并排序递归深度是 log n没问题但如果你把一个深度为 n 的递归写法用在链状数据结构上比如递归求二叉树的深度在树退化成链时深度可能达到 n而 n 到十万级别时栈就爆了。解决思路有三个把递归改成显式栈的循环在递归函数里加参数管理深度或者用非递归的迭代算法。对于深度可能很大的搜索我一般先估算递归深度超过一万的话就放弃递归。另外重复计算也是递归的超时根源。比如不带记忆的递归求解斐波那契数列时间复杂度是指数级n50 就要等半天。如果你在递归里多次进入相同的状态应该立刻想到记忆化搜索把返回值存在字典或数组里。这个习惯帮你把很多看起来没救的递归题救回来。4.2 复杂度估算失误错在“能跑通就行”课后作业最典型的错误不是代码写错而是复杂度选错。很多同学写完了样例觉得自己完成了结果交上去超时。原因很简单本地数据太小。例如一道题 n 达到 10^5你用 O(n²) 的暴力算法样例可能有 n100跑得飞快但隐藏测试数据一下拉满直接超时。判断一个算法能不能过需要脑子里有一个大概的执行速度量级。按目前的评测环境C 在一秒内执行大约 10^8 次简单运算Java 大概 10^7 到 10^8Python 明显更慢大概 10^7 以内才稳妥。因此拿到题目先做一道算术题如果 n10^5n² 是 10^10肯定不行如果 n log n 大约是 1.7×10^6可以。一旦发现你的算法在这个量级之外不要寄希望于评测机快立刻换思路。我见过有同学把 O(n²) 的剪枝优化到“看起来像 O(n)”但最坏情况仍然是 O(n²)结果被极端数据卡死。复杂度分析不能靠侥幸。4.3 边界条件与“差一个下标”的陷阱算法题里最常见的 bug 就是下标越界、空数组、或者二分查找的左右端点搞错。比如二分查找用 while l r 还是 while l r很多人每次都要现场试。这里有一个建议固定用 Python 的 bisect 标准库来处理递增序列的查找不要自己手写二分。如果作业要求你必须手写那就在草稿纸上用长度为 1、2、3 的数组把每一步 l、r、mid 的变化写出来对比你的循环条件。这个成本很低但特别管用。另一个频繁出问题的位置是动态规划数组的索引偏移。比如“编辑距离”的 dp[i][j] 表示前 i 个字符通常需要开 (n1)×(m1) 的数组而字符串索引是从 0 开始的。如果转移时直接用 dp[i-1][j-1] 对应字符串的 i-1 和 j-1逻辑上是对应的但如果你写成 dp[i][j] 表示当前处理位置就很容易整体偏移一位。我的习惯是在代码里明确注释两套索引的关系然后用一个特别小的用例比如 “” 到 “a”手动验证初始化和第一次转移。4.4 构造测试数据的几种高效方法除了随机对拍还有几类边界数据是每次作业提交前必须手工构造的。第一类是空输入比如空数组、空字符串、n0 的情况很多代码在这种输入下会直接越界。第二类是极值输入比如所有数字都相同、所有时间都重叠、图只有一个节点。第三类是反向数据比如输入已经按降序排列考验排序算法的稳定性或双指针的走向。另外如果你在做图论题一定要构造一个不连通的图确认算法能否正确处理未被访问的节点。如果你在做贪心题可以故意找一些“看似能贪但实际会错”的例子比如区间调度里按区间长度贪心会失败的数据。把这些测试数据一个一个小规模地喂给程序再用 print 或者调试器观察关键变量的值。这个过程虽然繁琐但能让你养成“逻辑先行”的习惯很多时候 bug 在写出来的瞬间其实就在这些边界里只是你没去点破。5. 课后作业之外的几点建议5.1 把作业模型映射到真实场景学完算法概论不能只把作业交了就完事。我经常和学生说题目里的抽象模型其实在现实系统里到处都有。加权区间调度就是会议室预定系统、任务编排工具的底层模型Dijkstra 算法就是地图导航和网络路由的雏形最长上升子序列的思路用在股票交易里的“最多完成多少笔”问题。作业的价值在于让你看见这个映射关系将来你在工程里遇到“选择一批不冲突的任务”“计算两个字符串的相似度”“给一批请求做优先级调度”第一反应不是搜索现成库而是意识到这不过是一个换皮版本的课后题。5.2 建立自己的算法解题模板库我建议准备一个本地笔记把每次作业里用到的核心结构记下来。不是让你背答案而是记录方法和为什么。比如“分区调度类问题排序 二分 dp关键是求上一个不冲突任务的位置”下面放一棵代码和复杂度分析“图论题看到 n 大先考虑稀疏图用邻接表看到负权边排除 Dijkstra 换 Bellman-Ford”。这样积累一个学期之后你就有了一本个人的算法手册它比你翻任何参考书都更贴合你自己的思维习惯。5.3 时间管理与合作边界最后说一个跟算法无关但比算法更重要的事。课后作业通常有严格截止时间难度又呈阶梯式上升所以一定不要拖到最后一天才动手。我的经验是每次作业发布的第一天就把所有题目读一遍给每道题估一个难度和时间列出哪个地方需要查资料。讨论题目是可以的但最终代码必须自己写过至少一遍否则考场上你会发现自己完全写不出来。不要直接抄同学的代码因为调试和答辩环节很容易暴露理解问题。你可以把交流重点放在“为什么这个状态定义合理”和“为什么这个复杂度能过”而不是复制粘贴。说实话算法概论这门课让我印象最深的不是期末考试而是每周那道让人咬牙切齿的课后作业。它逼着你把“听懂了”变成“写出来了”把“写出来了”变成“跑过了”把“跑过了”变成“复杂度和边界都站得住”。这里面最值钱的习惯其实就是每次拿到题目先写复杂度、再写代码写完代码后随手生成几组边界数据和对拍数据。如果你能坚持一个学期期末成绩只是一个附带的结果真正的收获是你看待问题的视角变了——再难的问题也不过是几个已知模型和优化技巧的组合。