第六章 算法设计范式：分治、动规、贪心、回溯与分支限界

第六章 · 算法设计范式：分治、动规、贪心、回溯与分支限界

本章要回答的三个问题：面对一个从未见过的问题，除了硬想和暴力，有没有可复用的"解题套路"？为什么有的问题能贪心一步到位、有的必须动规填表、有的只能回溯搜索？怎么判断手里的套路用对了没有？

为什么会有这一章

前五章是"兵器谱"：结构与算法一件件认识。这一章是"拳谱"：把散落各章的思路提纯成五套可迁移的解题范式——遇到新问题，先判断它长得像哪套拳，再动手。这不是投机取巧：范式是无数前辈问题解法的共性抽象，识别范式的眼光，正是"内功"与"招式"的分水岭。

五套拳一脉相承又各有禁区：分治把问题切成独立子问题（快排、归并的心法源头）；动态规划处理子问题相互重叠的情形，用表记账杜绝重复计算（1.3 节记忆化的正式版）；贪心每步取局部最优，只在贪心选择性质成立时正确；回溯系统性地试错与撤回，覆盖组合搜索；分支限界给回溯装上"预算评估"，剪掉注定失败的枝。选错范式，要么指数爆炸，要么答案根本不对。

五套拳之间有清晰的"降级链"：拿不准就先用最保守的搜索（回溯）保正确，再逐步升级——能证明贪心性质就贪心、能填表就动规、子问题独立就分治。本章各节的顺序正是按这条链从稳到快排布，读完你不仅会五套拳，还知道手里的题该降级还是升级。

读完能解决什么

对照开头的问题，本章的知识点清单如下：

• 能写出分治三段式（分解、解决、合并），用主定理的三个量级档位估复杂度；
• 能用归并的合并思想数逆序对，并解释"分治顺手做统计"的一般模式；
• 能陈述动态规划三要素（最优子结构、重叠子问题、无后效性），把斐波那契从递归改造成自底向上填表；
• 能手推 0-1 背包的转移方程、填出整张表、做空间滚动优化；
• 能区分贪心与动规的适用边界，举出贪心翻车的硬币反例，并给出交换论证的证明思路；
• 能写回溯模板（选择、递归、撤销），数出剪枝带来的搜索量差异；
• 能解释分支限界的下界函数如何剪枝，对比它与回溯的搜索树形状。

各节怎么分工

先决条件

• 第一章递归（五套拳有四套以递归为骨架）与复杂度推导；
• 第五章快排与归并（分治的现成教具）、堆（分支限界常配优先队列）；
• 2.5 节哈希表（记忆化的账本）与 3.4 节堆（限界的估价器）。

往下走到哪

本章出口通向两处：第七章的高阶结构（并查集支撑 Kruskal 的贪心、线段树是区间 DP 的表亲）直接消费这里的范式；工程上，版本对比的 diff 算法（分治/动规）、资源调度（贪心/动规）、约束求解与任务排布（回溯/分支限界）都是这五套拳的实战现场。学完本章，你面对陌生问题的第一反应将从"写循环试试"变成"这是哪类问题"。练法上给个硬指标：五套拳每套至少独立写一遍完整代码、跑一遍自造的小数据，光看懂不算数——范式的手感是写出来的，不是读出来的。

五套范式的关系图