这一篇在干嘛？
前九章是”招式”，本章是”内功”：面对没见过的问题，有哪几套可复用的思考框架？贪心（每步拿当前最优）、分治（劈两半递归）、动态规划（记住子问题答案）、随机化（用概率换确定性）、回溯（走不通就退）。每套配经典例题，看它们如何把指数级问题拉回多项式时间。
10.1 贪心算法：每步都拿眼前最优
贪心成立的前提：局部最优能保证全局最优（需要证明，如 MST 的切割性质），或问题只求近似解。
调度问题：短作业优先
单机调度最小化平均完成时间：把作业按服务时间升序排——交换论证：若相邻两个长前短后，交换后总时间严格变小。多处理机场景：作业有序后轮流分配（最小堆取最先空闲的机器）。
Huffman 编码：变长压缩的贪心典范
定长编码（ASCII 每字符 8 bit）对高频字符是浪费。前缀码：任何字符的编码不是另一个的前缀（用树的叶子区分，解码无歧义）。频率越高编码越短，总位数最小化——这就是最优前缀码问题。
Huffman 算法：维护一个按频率排序的森林，反复合并两棵最小的树（根频率相加）成新树，直到只剩一棵——正是第 6 章优先队列的主场：
白话：把最不常出现的字符压到树的最深处（编码最长），把高频字符捧到离根最近。合并两棵最小树的过程保证”最贵的字符代价最小化”——可以严格证明这是最优前缀码。（建堆 + N 次 deleteMin×2）。
装箱问题（Bin Packing）：贪心的近似艺术
把 个物品（体积 ≤1）装进最少单位箱——NP 完全，只能近似。三种在线贪心：
- Next Fit：装不下就开新箱，永不回头。最坏 最优（定理 10.1）。
- First Fit：依次找第一个装得下的旧箱。最坏约 倍最优。
- Best Fit：找装完后剩余最小的箱。表现与 First Fit 相当。
离线版（知道全部物品）：先降序排序再 First Fit（First Fit Decreasing），最坏约 最优 + 常数。反例证明贪心不完美（如 0.5, 2/N, 0.5, 2/N…序列）但很接近。
白话：贪心在 NP 完全问题上的正确姿势——不追求完美，追求”保证倍数”（approximation ratio）。这套思维在工程里无处不在：启发式调度、缓存淘汰、负载均衡。
10.2 分治：劈两半，各各击破
通用形式：。主定理（定理 10.6）：比较 与 —— 时 ； 时 ； 时 。
白话：三句话记主定理——“叶子重就听叶子的（递归项主导）""两边一样多一层 log""根重就听根的（切分工作主导）“。归并排序 ：a=2, b²=2，打平 → 。
最近点对：分治的经典
平面 N 个点找最近两点。暴力 。分治：按 x 排序劈两半递归；难点在跨越中线的点对——关键观察：若两侧各自的最小距离为 ，跨线点只需检查宽 的竖条带，且按 y 排序后每个点只需与后 7 个点比较（鸽笼原理：条带内同侧点两两距离 ≥ δ，一个 δ×2δ 方块最多装 4 个）。总复杂度 。
选择问题：中位数的中位数
线性时间找第 k 小：按 5 个一组取中位数，递归找”中位数的中位数”当枢纽，保证划分至少干掉 30% 的元素——。与第 7 章的 quickselect（期望 O(N)）互补：这是最坏情形 O(N)。
10.3 动态规划：用一张表换掉重复递归
识别特征：最优子结构 + 重叠子问题。朴素递归把同一个子问题算指数遍；DP 把答案存进表，每个子问题只算一次。
例一：斐波那契的救赎
朴素递归 fib(n)=fib(n-1)+fib(n-2) 是 （指数）。加一张表缓存（或自底向上循环）就是 ——“用表代替递归”是 DP 的最小形态。
例二：矩阵链乘法
乘法顺序不同，标量乘法次数天差地别（如 50×10 · 10×40 · 40×30：先乘前两个 35000 次，先乘后两个 22000 次——差 60%）。子问题定义： = 计算 的最少乘法次数，枚举”最后一次相乘的切分点 k”：
白话： 和 两块结果矩阵相乘的代价。按”子链长度”从 2 到 N−1 填表，。DP 套路：定义最优子问题 → 写出含 min/max 的递推 → 确定填表顺序 → 记录决策以便回溯最优方案。
例三：全源最短路（Floyd-Warshall）
第 9 章的 4 行三重循环就是 DP：，外层中转点 k。“允许经过的前 k 个中转点”是子问题的递进维度——、原地更新。
DP vs 贪心 vs 分治：贪心不回头（要求可证明的局部最优）、分治子问题独立、DP 子问题重叠且需要全部枚举决策点。
10.4 随机化算法：用骰子换性能
随机数发生器：线性同余 （如 ，）——同一 seed 序列可复现（调试友好，密码学不安全）。
跳表（Skip List）：抛硬币做出来的平衡
有序链表 + “高速公路”：每个节点以 1/2 概率额外长出更高层的指针（链接到前方 2 格、4 格……的节点）。查找从最高层向右冲、冲不过就下一层——期望 ，无需旋转、实现比 AVL/红黑树短得多，并发友好（Redis 的 zset 底层就是它）。
随机化素性测试（Miller-Rabin 思路）
大数素性是 RSA 的地基。费马小定理：p 为素数时 。随机取多个 a 检验，失败多次则 p 几乎必为合数——概率换时间，错误率可压到任意低（2^-50 级），远快于确定性试除。
白话：随机化三板斧——快速幂+取模检验（素性）、抛硬币建层（跳表）、随机枢纽（quickselect/快排）。共同点：单次可能不走运，期望/高概率表现极好，且对手无法构造最坏输入。
10.5 回溯：走不通就退一步
思想：DFS 枚举解空间，剪枝（pruning）提前掐死不可能的分支。适合 NP 完全问题的”精确解”需求——指数最坏，但剪枝后实战常很快。
公路收费重构（turnpike）：给出点对间所有 个距离，还原各点坐标。从”最左边 = 0、最右边 = 最大距离”开始，每次尝试放置下一个点并校验全部新距离是否在集合中，失败即回溯。
博弈树（games）：双人博弈的极小极大搜索——我方选让己方分最高的，对方选让己方分最低的，递归到底。α-β 剪枝：当某分支已被证明不优于已算出的选择时，整棵子树不搜——同样的结果，搜索量砍一个数量级（象棋/五子棋 AI 的底层）。
白话：回溯 = 带记忆的暴力。三件套：候选生成 → 约束剪枝 → 递归 + 撤销。“撤回”是关键——状态改动必须可逆（或用局部拷贝）。
常见坑
① 贪心不证就用：装箱 First Fit 有 17/10 倍的最坏保证，但”拍脑袋贪心”可能毫无保证——用贪心前先想交换论证或找反例。② DP 忘了自底向上的填表顺序：算 C[i][j] 时子问题必须已就绪，矩阵链按”链长”枚举就是这个原因。③ 回溯不撤销状态：递归返回后棋盘/标记数组没恢复原样，分支间互相污染，解全错。
通关标准
学完本篇你应该能做到：① 用优先队列手写 Huffman 构造并证明其最优性直觉；② 背出三种装箱贪心的保证倍数与降序优化的意义；③ 用主定理三句话判定分治复杂度；④ 面对一道新题，按”贪心→分治→DP→随机→回溯”的顺序判断适用性并说出理由；⑤ 手写矩阵链 DP 的状态定义与转移方程。
Huffman 算法为什么选"最小的两棵"合并而不是随便两棵？
最优前缀码中频率最低的字符必然在树的最深处且互为兄弟（可交换论证）。不断合并最小者正是逆向构造这棵树：最浅的权值给高频字符，总编码长度（外路径加权长）最小。
装箱问题是 NP 完全的，"降序 + First Fit"凭什么还能用？
它是近似算法：不承诺最优，但保证不超过最优的 11/9 倍加常数。工程上”接近最优 + 快”往往优于”精确最优 + 指数时间”。
动态规划和分治的本质区别是什么？
分治的子问题相互独立（如归并的两半），不重复；DP 的子问题大量重叠（如矩阵链的 C[i][j] 被多个父问题引用），必须缓存。重叠子问题 + 最优子结构是 DP 的识别特征。
跳表为什么能达到期望 O(log N)？
每个节点出现在第 k 层的概率是 2^-k，第 k 层期望节点数 N/2^k，查找路径在每层期望只走常数步、共 log N 层——几何分布的期望求和。
α-β 剪枝会改变极小极大的计算结果吗？
不会——被剪的子树不可能影响根的取值（已有更优选择）。它只减少搜索量，博弈值与完整搜索完全一致；剪枝效率越高（好的走法排序），砍得越多。