1. 先搞清楚事情的本质“一般方法”到底是一门什么样的课每年SCAU的算法设计与分析开课总有一批同学带着“我又要学一堆算法了”的心态坐进教室结果翻到《一般方法》这一章发现既没有复杂的代码也没有玄妙的数学公式反而觉得“这不就是些思想嘛看看就会了”。等到课后作业和上机实验一做立刻露馅——面对一道新题脑子里知道有分治、贪心、动态规划这些名字但就是不知道哪个能用、哪个能用对、哪个能跑得动。我当年也是这么过来的。所以在聊具体内容之前我想先把“一般方法”这四个字掰开揉碎说清楚。它不教你怎么写某一个具体算法而是教你怎么面对一个从没见过的算法问题从问题描述出发找到适用策略的思考路径。换句话说数据结构课学的是“存”算法课学的是“算”而“一般方法”这一章学的是“怎么想”。这门课适合三类人一是正在SCAU修这门课、想把理论吃透的学生二是准备考研复试或找工作笔试、需要系统梳理算法设计思路的人三是工作中遇到性能瓶颈、想从“调库”走向“设计方案”的开发者也值得回头补这一课。它不会直接让你写出某个框架但它会改变你面对算法题时的第一反应——从“我见过类似的吗”变成“这个问题的结构适合哪种策略”。这一章之所以叫“一般方法”核心在于它提炼出了几类解决计算问题的高层策略。我把它理解为四个字“先分后合”“步步贪心”“状态累积”“系统搜索”。后面每一类我都会展开讲。但在进入策略之前必须先建立统一的复杂度标尺否则你连“这个方法好不好”都判断不了更谈不上选择。这就是我安排下一节的逻辑。2. 复杂度分析选方法之前先得有“标尺”2.1 渐近记号大O、Ω、Θ到底在表达什么算法设计与分析这门课分析是设计的裁判。你设计了一个算法怎么证明它好不是跑一次看时间就行而是要从数学上估算它在最坏情况下需要多少基本操作。这里引入的渐近记号本质上是在忽略常数和低阶项只关注输入规模趋向无穷大时增长率的主导项。大O记号表示上界即“最多不会超过这么多”。比如T(n) 3n² 2n 1当n很大时低阶项和系数影响微弱所以T(n) O(n²)。Ω记号表示下界即“至少不会少于这么多”。使用场景多用于证明算法的下限比如基于比较的排序下界是Ω(n log n)意味着任何比较排序都无法突破这个量级。Θ记号表示上下界同阶即复杂度的“精确刻画”。当算法的最好与最坏情况增长率一致时就能用Θ表示。别小看这三个记号的区别。考试里经常有同学把所有情况都写大O但判定一个算法“是否最优”时必须用到Ω。比如你证明归并排序是O(n log n)这只能说它不快于这个界你还要说明基于比较的排序不可能低于Ω(n log n)才能体现它的最优性。这两个记号配合使用才有说服力。2.2 复杂度层级的感觉从微秒到宇宙年龄纸上谈兵容易让人对复杂度失去感觉。我讲课或写博客时喜欢用一张心智表帮大家建立直觉复杂度典型算法n100时粗略量级能否接受O(1)哈希表查找1极佳O(log n)二分查找约7步极佳O(n)线性扫描100步良好O(n log n)归并排序约664步良好O(n²)冒泡排序10000步要考虑O(2ⁿ)子集枚举约10³⁰基本不可行O(n!)全排列约9×10¹⁵⁷不可能这个表的左侧是理论右侧是体感。很多同学写回溯法的时候总觉得“我剪枝了应该就快了吧”但如果你没做复杂度分析就交出作业一旦输入规模达到20程序就跑不动了。这不是编译器的问题是你选择的策略本身就不适合这个规模。复杂度分析的价值就是让你在写代码之前就知道这条路走不走得通。我在实际学习中还有一个体会递归方程式的求解代入法、递归树法、主定理是这门课里最需要手感的工具。主定理尤其值得掌握——它能让你一眼看出形如T(n) aT(n/b) f(n)的递归式对应哪个复杂度等级。考试和实际分析中八成以上的分治算法都能套主定理不用每次费劲展开递归树。3. 核心策略拆解分治、贪心、动态规划、回溯与分支限界怎么选3.1 分治法把大问题切成互不相干的小块再合并成整体分治法的核心就一句话如果一个大问题的子问题互相独立且结构与原问题相同就递归地求解子问题再合并结果。它的难点不在“切”而在“合”。比如归并排序切分是容易的真正花功夫的是合并两个有序序列。又比如计算数组的逆序对数量朴素做法是双重循环O(n²)用分治可以在归并排序合并的间隙统计跨两半的逆序对复杂度降到O(n log n)。使用分治法时你必须回答三个问题子问题怎么划分子问题的解怎么合并成原问题的解递归基base case是什么这三个问题没想清楚就动手写递归很容易写出“逻辑正确但合并时算错”的代码。以最接近点对问题为例经典做法是按x坐标分成左右两半递归求两侧最小距离然后合并时只需检查中线两侧距离小于当前最小距离的点带这段扫描的常数优化是整个算法性能的关键——少了这一步分治就退化成了暴力。我曾经踩过一个大坑写二叉树相关问题时强行分治结果根本没有把问题拆成互相独立的子问题代码里全是共享状态的全局变量最后调试到崩溃。后来我才总结出分治的适用前提子问题必须独立。如果子问题之间有重叠那就别用分治往下看动态规划。3.2 贪心法每一步都选当前最优但前提是局部最优能导出全局最优贪心法的诱惑永远很大因为它实现最简单排序一遍然后线性扫描做选择没有递归没有记忆化表代码短跑得快。但它也是五类方法里最容易“想当然”的一个。活动选择问题是教科书里的经典按结束时间排序每次选最早结束且与已选活动不冲突的活动就能得到最大兼容子集。这里的关键不是“怎么选”而是为什么要按结束时间排序而不是按开始时间或持续时间。因为早点结束能给后续活动留下更大空间这个直觉可以通过交换论证严格证明。Huffman编码是另一个例子。它每次合并频率最低的两个节点构造出的二叉树能保证带权路径长度最小。如果不满足“每次最小的两个”这个贪心选择比如为了编码美观强行平衡树那压缩率就会下降。贪心法的证明分两部分一是贪心选择性质第一个选择可以是贪心选择的二是最优子结构去掉第一个选择后剩余子问题仍可用贪心。考试中这两个证明步骤是高频考点但工作中很少人会写证明所以我给你一个实用守则在采用贪心之前先想一个反例。如果无法在几分钟内构造出反例再动手写代码如果构造出来了立刻转向动态规划。这里要特别提一个经典误导案例——找零钱问题。在面额为1、5、10、20、50的货币体系里贪心选最大面额是对的但在某些特殊面额组合如1、3、4的体系里要找6元贪心会先拿4再拿两个1共3枚而最优解是两个3共2枚。这就是贪心失效的典型。你把这类反例积累多了选型时会自然多一分警惕。3.3 动态规划重叠子问题才是它的主场如果说贪心是“短视的乐观主义”动态规划就是“持重的记账式决策”。它适用于子问题重叠、且具有最优子结构的问题。所谓最优子结构就是原问题的最优解包含子问题的最优解所谓重叠子问题就是递归过程中同一个子问题会被反复求解多次。记忆化搜索和自底向上的填表是两种实现方式后者经常更直观且性能更稳定。以0-1背包问题为例。dp[i][j]表示前i件物品在容量j下能获得的最大价值状态转移方程是dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])。这个方程看起来简单但背后有几个容易被忽略的问题为什么第二维要从大到小倒序更新因为如果正序更新dp[i-1][j-w[i]]可能已经被本轮覆盖成了dp[i][j-w[i]]相当于同一件物品被选了多次那就变成完全背包了。这就是初学者经常混淆0-1背包和完全背包的根本原因。矩阵链乘法是课堂上用来强化“填表次序”的例子。它的dp[i][j]表示链Ai...Aj的最少乘法次数转移时枚举分割点k。这里有个反直觉的点虽然问题规模小的区间先算但循环次序不是按i从1到n而是按区间长度len从2到n递增。如果你照搬0-1背包的双重循环顺序就会访问到还没计算的状态结果全错。动态规划的学习我给一个可复盘的路径拿到题目先写暴力递归版本然后检查递归树里是否有重复计算的节点如果有加一个备忘录记忆化就能运行最后把递归结构改成填表循环顺便压缩空间。这套三步走的方法成功率极高本质上是把一个不知道怎么设计DP的问题强行降维成“先暴力再查重再优化”。3.4 回溯法系统搜索解空间剪枝才是灵魂回溯法可以理解为你拿着一个手电筒在解空间树上模拟深度优先遍历每到一个节点判断是否还有希望没希望就掉头回溯。它在n皇后、图的m着色、全排列生成、子集和问题中都有大量应用。很多初学者把回溯法等同于“用递归列举所有可能”这句话没错但只说对了一半——回溯的真正价值是通过约束函数和限界函数砍掉大量不可能的分支否则它只是暴力枚举换了个马甲。以n皇后问题为例如果不剪枝解空间是n^n量级加上“不同列、不同对角线”的剪枝之后实际搜索的节点数急剧下降。实现时的判断技巧很经典对于第i行放到第j列如果之前第k行皇后在q[k]列那么同一个主对角线满足i - j k - q[k]副对角线满足i j k q[k]。用这个规则可以在O(1)时间内完成冲突检测而不是每放一个皇后就扫描整个棋盘。回溯法在课程设计或竞赛中的表现很依赖剪枝顺序。一个实用的经验是优先搜索更有希望的方向。比如解数独时先填候选数最少的格子这能把搜索树剪掉一大截。这个技巧在书上很少写但在“一般方法”这一章之后做实验时你会体会到同样的剪枝思路在不同问题上的威力。3.5 分支限界法回溯的兄弟但搜索策略换成了广度优先分支限界和回溯的核心区别在于搜索策略回溯是深度优先一直往下探分支限界是广度优先或以最小耗费优先的方式逐层扩展并且用限界函数剪掉得不到更优解的结点。在以队列实现时分支限界法适合求最优解以优先队列实现时它有点像“A*算法”的亲兄弟——每次扩展当前代价最小的节点目标是在找到第一个解时就确保这个解是最优的。课堂上最常拿0-1背包来做对比。回溯法在搜索过程中不断更新上界一旦当前价值加上剩余物品的可装入上界不超过已找到的最好值就剪掉分支限界法则在优先队列中按“当前价值剩余物品价值上界”排序优先扩展上界最大的分支。两者都能得到最优解但分支限界常常能更早收敛。我个人的看法是真实工程里分支限界写起来比回溯繁琐但如果你设计的状态空间很大且需要全局最优那就值得用。平时练习时我建议至少手写一遍队列版本的分支限界不是为了考试而是为了建立“逐层打开状态空间”的直觉。3.6 让策略对比可视化一张表帮你快速定位学完五种方法后最容易出现的困境是“单个方法都看懂了遇到题目却不知道用哪个”。我整理过一张对照表基本能解决七成选型问题方法适用前提需要特别注意典型问题分治子问题独立、结构相同合并过程必须正确归并排序、最近点对贪心局部最优能推出全局最优需要证明注意反例活动选择、Huffman编码动态规划子问题重叠、最优子结构状态定义与转移顺序0-1背包、矩阵链乘回溯搜索空间可系统遍历剪枝函数的强度n皇后、图着色分支限界求最优解、空间可分层限界函数设计0-1背包最优解这张表不是让你背的而是提醒你一个道理每种方法都有最适配的问题结构。拿到一个问题先判断它的结构而不是拿熟悉的方法往上套。你把这个习惯养成了这门课的主干就算通了。4. 从题目到方法面对一道新题时的决策顺序4.1 先问五个问题而不是先写代码很多人做算法题的坏习惯是读题两分钟就打开编辑器开始敲循环。我理解那种急切感但以我踩过的坑来说写代码前花10分钟做结构判断远比写完之后再回炉重造划算。拿到一个新问题我建议按顺序问自己下面几个问题问题是否可以从输入中拆出多个互不相干的子问题如果可以子问题是否与原问题同构——这指向分治。问题的决策是一个接着一个做的吗每一步选“当前最好的”之后剩余部分还是同样的问题吗这指向贪心。同一个中间状态会不会被反复用到比如同样的剩余容量、同样的字符串前缀在不同的路径里反复出现这指向动态规划。所有可行解能否组织成一棵搜索树每个节点的解是否可以被约束条件排除一部分这指向回溯或分支限界。数据规模有多大n≤20基本可以接受指数级枚举n≤10⁵就必须设计O(n log n)甚至O(n)的算法。这个问题能把前面的候选集进一步缩小。这套提问框架并非玄学它本质上是把五种方法各自的适用前提翻译成了一套可操作的体检流程。你练熟了之后会发现大多数题在问完前三个问题时就已经有了方向。4.2 用0-1背包演示一遍全过程我拿0-1背包作为演示有一个承重W的背包和n件物品每件物品有重量wᵢ和价值vᵢ问能带走的最大价值。子问题独立吗不独立。第i件物品选与不选会影响后续容量而且不同选择路径可能到达同一个剩余容量状态说明子问题有重叠。所以分治不适合直接套。局部最优能推出全局最优吗不能。比如容量有限时单件价值最高的物品不一定比“两件次高但总重更合适”的物品好。所以贪心大概率失效。状态能否被定义能。dp[i][j]就是明确的中间状态。选i和不选i两种决策导出转移方程重叠子问题自然出现。这就该用动态规划。整个过程不是玄学是一步一步把题目代入五种策略的适用条件做筛选。你每做一道题都强迫自己走一遍这套流程很快就能形成肌肉记忆。4.3 一个容易被忽略的环节先把暴力解法写对我说一个很多教材不强调但实际非常好用的经验当你不确定该用动态规划还是贪心时先写一个正确但慢的解法。慢到能跑通小规模数据就行。它有两个价值一是作为基准用例用来验证后续优化版本的正确性二是你盯着暴力递归的结构往往能看出来重叠子问题藏在哪儿。很多DP状态转移方程我是靠“先写暴力再加缓存”才推出来的。这个成本很低但收益极高强烈建议你试一试。我在帮学弟学妹改作业时发现他们最常犯的错不是不会设计算法而是跳过了暴力基准直接写DP结果状态转移方程写错了都不知道。等到测试样例一跑发现答案不对又没法判断是转移方程的问题还是边界条件的问题。如果能先有暴力解兜底这类问题几分钟就能定位。5. 这门课怎么学才能不白学一些不容易被讲清楚的实战经验5.1 伪代码不要跳着看每一行都要翻译成真实逻辑SCAU的算法课考试里伪代码题是重头戏。很多同学觉得伪代码像英文缩写扫一眼“看懂了”就过去。但真让你上机实现时才发现伪代码里一句“将A[i]插入有序序列”会带来一整块被省略的复杂度控制逻辑。我的建议是每个算法的伪代码都要自己翻译成一遍可运行的真实代码跑通几个用例后再回头对比教材。这个过程很花时间但它能把“视觉上的熟悉”变成“能力上的掌握”。尤其是在分治和DP这两块只有亲手写过合并逻辑或填表循环你才会知道那些看似平淡的细节才是整个算法最脆弱的环节。比如归并排序的合并循环里左半或右半先耗尽时的处理比如矩阵链乘的区间长度循环上限这些都是教材里一句话带过、但代码里必出bug的地方。5.2 复杂度分析不要只背结论要把推导过程自己在纸上走一遍主定理很好用但如果你从不看它的证明过程遇到主定理覆盖不到的情况比如递归方程里有取整函数、有常数扰动就会慌。我的做法是每个重要算法都自己推导至少一次复杂度。归并排序用递归树展开第0层规模n第1层两个规模n/2第2层四个规模n/4每层总代价都是n树高log n所以总代价是O(n log n)。这一遍推导下来你会对为什么要用归并而不是简单递归有更深的体感。快排的最坏情况也要自己推一次如果每次划分都极度不均衡递归树退化成链复杂度变成O(n²)。理解了这一点你就会明白为什么随机化快排有意义为什么工程实现里要三数取中。这些经验不是教材直接告诉你的但它恰恰是你设计或选择算法时真正的竞争力。5.3 上机实验的正确打开方式先写样例再写代码最后玩边界实验课永远是“看着会了一跑就废”的重灾区。我的建议是三步走第一步题目读完后先手算三个样例包括一个最小规模、一个常规规模、一个能触发边界条件的特殊场景第二步按伪代码实现算法跑通这些样例并记录输出第三步故意往输入里塞极端值比如空数组、全是重复元素、n取上限、物品重量等于背包容量等看程序会不会崩溃或出现非预期结果。拿排序算法举例全重复数组是快排序的噩梦拿0-1背包举例所有物品重量都为0时DP数组的语义会变得奇怪拿n皇后举例n1时回溯是否直接输出解。这些边界场景看着琐碎但在实际工程里出问题的从来不是常规路径而是边界条件。课程实验不会告诉你这些你需要主动找它们。还有一个小技巧在代码里临时加一个计数器统计“状态被访问的次数”或“回溯函数被调用的次数”打印出来观察它是否符合你的复杂度预期。比如回溯法如果剪枝做得足够好调用次数应该远小于解空间总量如果调用次数接近总量说明你的剪枝条件多半形同虚设。这种验证方式比单纯跑时间更精准真正体现了算法设计与分析这门课的思想——用数学预估用实验校验。5.4 把“一般方法”当成工具书而不是小说最后说说我的整体学习体会。这门课的所有策略本质上都是处理“计算复杂度”这头怪兽的工具它们没有绝对的高低之分分治不一定比贪心高端DP也不一定永远比回溯更快。真正的能力在于遇到新问题时能根据结构快速定位候选工具然后用复杂度分析判断它是否可行最后用实验验证它确实站得住。我当年学这章时最大的收获不是记住了五种方法的名字而是养成了一个习惯任何算法拿到手先追问它为什么适用于这个问题——是子问题的独立性是结构的重叠性还是剪枝的强度这个问题问多了算法思维才算真正入了门。希望你学完“一般方法”之后也能再从一道题里看到它背后的结构而不是只记住答案的样子。