第 5 章 设计算法 — 递归、动态规划、蛮力与贪心Copy Anchor Link

这一章讲什么: 面对一个全新问题,怎么想出解法。书里给了五类策略: 递归(以及它长出的分治/减治)、回溯、动态规划、蛮力搜索、贪心算法, 每类配 2–3 个完整例子。它在全书链条里的位置:工具箱章—— 第 6–9 章的具体算法(排序、选择、洗牌、搜索)全是这些策略的实例, 第 12–17 章的数据结构算法里也到处是本章的手艺。

1. 顶层全景Copy Anchor Link

  一个递归函数的两类情况:基础情况(直接解) + 递归情况(用更小的同类问题)
      │
      ├─ 减治(decrease-and-conquer):只解一个更小版本 → 阶乘、二分搜索
      ├─ 分治(divide-and-conquer):解多个更小版本 → 斐波那契、汉诺塔、归并/快排
      ├─ 回溯(backtracking):试错+撤销 → 迷宫、凑数谜题
      ├─ 动态规划(DP):子问题存起来不重算 → 斐波那契加速、断行
      ├─ 蛮力(brute force):全排列试个遍 → 重言式、字母算式(阶乘级,慎用)
      └─ 贪心(greedy):每步取当前最优 → 找零、最近邻旅行商(可能不最优!)

  图说:左边三个是「递归家族」,右边三个是「搜索家族」。
  全书后文反复回到这张表:快排是分治、堆调整是减治、图遍历是回溯、拓扑排序接贪心。

2. 主线例子:斐波那契数,从朴素递归到动态规划的完整改造Copy Anchor Link

选斐波那契当主线,因为原书拿它把「递归 → 发现性能缺陷 → 动态规划修复」 走成了完整一圈¹:

数列定义:F₀=0,F₁=1,之后每一项是前两项之和:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55…²

第 ① 步:朴素递归版。 直接翻译定义:

const fibo = (n) => {
  if (n === 0) { return 0; }
  else if (n === 1) { return 1; }
  else { return fibo(n - 1) + fibo(n - 2); }
};

对、短、不可能写错——但慢。算 fibo(7) 的调用树里,fibo(5) 算了两次, fibo(3) 算了五次,fibo(2) 算了八次³。 总调用数 C(n) 满足 C(n) = C(n−1) + C(n−2) + 1,解出来 C(n) = 2·Fibo(n+1) − 1 (习题 5.4 的答案)——指数级。算 fibo(50) 要万亿次级调用,天荒地老。

第 ② 步:记忆化(memoization)——给纯函数装缓存。 这是第 2 章高阶函数

• 闭包的直接应用,全书最美的 8 行代码之一⁴:

const memoize = (fn) => {
  const cache = {};
  return (...args) => {
    const strX = JSON.stringify(args);
    return strX in cache
      ? cache[strX]
      : (cache[strX] = fn(...args));
  };
};

const fibo = memoize((n) => { /* 原样递归体 */ });

走一遍 fibo(7):第一次调用一路递归下去,但每个 fibo(k) 算出后都存进 cache(键是参数序列化成的字符串,值是结果);之后任何重复的 fibo(k) 都是一次查表。每个值只真正计算一次——时间从指数级降到线性级, fibo(100) 立即返回⁵。 缓存放在闭包里,外面看不见、也碰不到(第 1 章闭包一节的实战)。

第 ③ 步:制表(tabulation)——自底向上,连缓存表都省了。

const fibo = (n) => {
  if (n < 2) { return n; }
  let a = 0, b = 1;
  while (n > 1) { [a, b] = [b, a + b]; n--; }
  return b;
};

从最小的值往上滚:[a, b] = [b, a+b] 是解构交换的推广(第 1 章笔法)。 注意它根本不存历史值——因为斐波那契只需要最近两个数。 这暴露了记忆化与制表的真正分工(书里的原话要点):记忆化严格只算需要的 但有递归开销;制表可能算多了但没有递归、通常更快⁶。

第 ④ 步:同一招用到「区间求和」。 断行问题需要频繁问「第 x 到 y 个块共多宽」。 三个版本递进:朴素循环 O(n) → 记忆化递归(「0 到 q 的和 = 0 到 q−1 的和 + arr[q]」, 多次询问后摊还 O(1))⁷ → 制表预计算前缀和, IIFE + 闭包把 partial 表藏起来,查询恒 O(1)⁸。 第 4 章「预计算换查询」在这里有了第三个名字:自底向上动态规划。

3. 核心原理Copy Anchor Link

3.1 递归的四步构造法Copy Anchor Link

写递归函数不靠灵感,靠流程。书里给的流程看似循环论证,实为最强心法⁹:

1. 假设你已经有一个能解这个问题的函数(就是你要写的这个);
2. 找出能直接解的基础情况(不必再递归的小输入);
3. 想出怎么把原问题化解成一个或多个更小的同类问题;
4. 调用 ① 假设的函数解决 ③ 的小问题,小到头就直接解。

阶乘是样板:n! = n × (n−1)!,基础情况 0! = 1(「书架空着的排法只有一种」)。 代码与定义逐字对应,所以「很难写错」¹⁰。 书里补了递归的「全能性」:任何能用循环写的都能用递归写,反过来也行; Haskell 之类的语言甚至没有循环、只有递归。

3.2 减治与分治:递归的两个量级Copy Anchor Link

两者都是「化小」,区别在化几个:

• 减治(decrease-and-conquer):只用一个更小版本——阶乘、二分搜索、 遍历任务清单;书里也叫它「分治的特例」¹¹。
• 分治(divide-and-conquer):用多个更小版本——斐波那契(两个)、 归并排序与快排(第 6 章)、汉诺塔(下面走一遍)。

汉诺塔走查(3 根柱 A/B/C,n 个盘从 A 移到 C,大盘不能压小盘):

const towers = (disks, origin, extra, destination) => {
  if (disks > 0) {
    towers(disks - 1, origin, destination, extra);   // ① 上面 n−1 个挪去中转柱
    console.log(`Move disk ${disks} from ${origin} to ${destination}`);  // ② 最大的挪去目标柱
    towers(disks - 1, extra, origin, destination);   // ③ n−1 个再挪回来压住
  }
};

towers(4, "A", "B", "C") 输出 15 步(2⁴−1)。为什么是 2ⁿ−1? 递推 M(n) = 2M(n−1) + 1:两次搬 n−1 个盘加搬一次最大的¹²。 书里附了那个著名的尾声:64 个金盘的版本,一秒一步要 2⁶⁴−1 秒, 五千八百亿年以上——指数级的直观尺度¹³。

3.3 回溯:选一条路,死路就撤销重选Copy Anchor Link

回溯(backtracking) 的模式:面临多个选项时选一个先试; 成功就收工,失败就回到当初做选择的地方换下一个;选项耗尽则整体无解¹⁴。

迷宫的伪代码骨架(第 17 章会给完整图算法):到目标?成功。 否则标记当前格已访问,对每格邻居递归试;哪个邻居返回了路径就返回; 全失败返回 null——null 一路冒泡上去,就是「撤销」的实现¹⁵。

Sam Loyd「海滩打娃娃」谜题(击倒几个编号娃娃凑满 50 分)是完整代码版:

const solve = (goal, standing, score = 0, dropped = []) => {
  if (score === goal) { return dropped; }                        // 正好达标
  else if (score > goal || standing.length === 0) { return null; } // 超了/没选项了:失败
  else {
    const chosen = standing[0];
    const others = standing.slice(1);
    return (
      solve(goal, others, score + chosen, [...dropped, chosen])  // 先试:选第一个娃娃
      || solve(goal, others, score, dropped)                     // 失败回溯:不选它
    );
  }
};
solve(50, [15, 9, 30, 21, 19, 3, 12, 6, 25, 27]);

|| 串联就是回溯的骨骼:左边(选了它)返回 null 才轮到右边(不选它)。 习题 5.3 的变体(射箭可重复命中同一环)只要在递归里加一支「再试同一选项」的递归 或把选项列表复制多份,骨架原封不动¹⁶。

3.4 蛮力搜索:全排列的两张脸Copy Anchor Link

蛮力 = 系统性地试所有组合。问题只有一个,但致命:组合数爆炸。

脸一:重言式判定(指数级 2ⁿ)。 n 个布尔变量的表达式是否恒真? 递归地对每个变量先试 false 再试 true,全真才算重言式; 一旦发现一个反例立刻短路返回¹⁷。

脸二:字母算式(阶乘级 n!)。 经典题 SEND + MORE = MONEY: 每个字母对应一个不同数字,求使等式成立的对应。10 个数字的全排列共 10! = 3,628,800 种, 逐个检验。检验函数直白:拼出 SEND、MORE、MONEY 三个数,首位为 0 直接拒, 否则看等式¹⁸。解:S=9, E=5, N=6, D=7, M=1, O=0, R=8, Y=2 (9567 + 1085 = 10652)。

全排列的生成本身是个 14 世纪 Narayana Pandita 的四步算法: 从右找第一个「上坡」d[p] < d[p+1] → 从右找比 d[p] 大的最小值 d[q] → 交换 → 翻转 p 之后。 书上拿 8403976521 → 8405123679 完整走了一遍¹⁹。

边界(书里明写):这个类别的算法「阶数落入指数或阶乘级,输入稍大就不可用, 所以本书其余部分会避开这类代码」——蛮力在这本书里的角色是反面教材²⁰。

3.5 贪心算法:每步最优,全局可能不最优Copy Anchor Link

贪心(greedy) 的规矩:每到一个需要做决定的地方,选当下看起来最好的选项, 不回头、不试探。快,但可能翻车——「贪心算法可能(也可能不)达成目标」是定义的一部分²¹。

三个例子画出它的适用边界:

1. 找零(成立但有条件):每次尽量用最大面额。$229.60 = 2×$100 + $20 + $5
   • 4×$1 + 2×quarter + 1×dime,张数最少,成立。 但换一个币制就翻车:有 $9/$8/$1 的国家,付 $16,贪心给 1×$9+7×$1(8 张), 最优是 2×$8(2 张)²²。
2. 旅行商(通常不最优):每步去最近的未访问城市。快,多数时候不错, 但不保证最短——这是 NP 难问题,精确解要蛮力全排列²³。
3. 最小生成树(成立且可证):给若干房子沿已有道路铺电缆,总成本最小。 Kruskal 算法(第 17 章实现)也是贪心——每次选最便宜的、不成环的路段, 而这个贪心保证最优²⁴。

适用边界的规律(补充,不在书里明说,来自通用知识):贪心能赢的问题都有 「贪心选择性质 + 最优子结构」;书里用三个例子的事实差异(找零看币制、 旅行商看运气、生成树保证)让读者自己摸到这条线,但没给判别定理。

3.6 断行问题:动态规划的实战规模Copy Anchor Link

值得单独走一遍,因为它是「DP 不只是斐波那契」的证据:给宽度不定的表单字段断行, 要求右对齐且空白惩罚最小²⁵:

• 输入:块宽 [7, 2, 5, 3, 6],行宽上限 MW=10;
• 行成本 = 行尾空白²(平方让「分散的小空白」优于「集中的大空白」: 两个空格放一行 2²=4,分放两行 1²+1²=2);
• 递归:costOfFragment(p, q) = 若 p..q 放得下则成本 (10−宽)², 否则在 p..q 间枚举断点 r,取左右成本之和的最小值;
• 结果:成本 19,断点 [0, 2, 4]——即 [7] / [2,5] / [3,6],验证: (10−7)² + (10−7)² + (10−9)² = 9+9+1 = 19; 对照另两种三行排法 21 和 25,确实最优²⁶。

和斐波那契同病:子段成本被重复计算(如 (5,3,6) 出现多次), 套一层 memoize 即修复²⁷。习题 5.5 的优化更妙:循环里一旦 累计宽度超过 MW 就 break——越往右只会更宽²⁸。 书里注明这是 TeX 排版算法(Knuth-Plass)的同族问题。

4. 作者的判断与证据Copy Anchor Link

• 「递归实现很难写错」是反复声明的经验判断(阶乘、斐波那契两处都说了), 依据是「逻辑与定义逐字对应」;反例(忘写基础情况)本章未讨论,见局限¹⁰。
• 蛮力被明确定位为反面教材:「结果算法的阶数通常落入指数或阶乘级…… 本书其余部分会避开这类代码」——少见的、旗帜鲜明的「别学我」²⁰。
• 贪心的边界用三个例子的事实差异呈现,不给判别定理——这是教学取舍: 记住三个案例的三种结局,比记住一个定理对初学者更有用,但形式化工具缺失。
• DP 两路线的取舍有明确口径:记忆化严格按需但有递归开销,制表可能多做但更快 ⁶;断行题里还演示了「记忆化能套在任何纯函数上」的通用性。
• 习题答案补充了硬事实:fibo(7) 共 41 次调用、C(n)=2Fibo(n+1)−1²⁹; 汉诺塔人手解法(最小盘循环移动)³⁰。

判断(我们的,不是书里的): 本章的编排顺序(递归 → 回溯 → DP → 蛮力 → 贪心) 是一条精心设计的性能焦虑曲线:先给你最优雅的武器,再让你亲眼看到它爆炸 (fibo 调用树),然后递上修复工具(DP),最后把「不惜代价试个遍」和 「赌一把当前最优」放在光谱两端示众。这个顺序比按字母表讲策略高明得多。 如果错,会错在: 焦虑曲线对自学者有效,但对已经见过这些策略的读者是冗余; 且本章每个策略都浅尝辄止,读者若只读本章会产生「我懂了」的错觉—— 真正的掌握要看第 6–17 章里这些策略反复出场后的复盘。

5. 边界与局限Copy Anchor Link

• 尾递归、递归深度限制没讲:JS 引擎对调用栈深度有限制(深递归会爆栈), 本章所有递归都很浅,问题没暴露;也没有讲尾调用优化(ES2015 规定了但引擎普遍未实现) ——这是补充(不在书里,来自通用知识)。
• 蛮力与贪心的理论边界没给:没有 NP 完全性的概念框架,读者不知道 「旅行商为什么不能贪心解决」是结构性原因而非运气。
• 动态规划没有系统性框架:没有「状态定义 → 转移方程 → 边界 → 顺序」的标准四步, 靠三个例子悟;习题答案里的优化(break 剪枝)也只给代码不给原则。
• 回溯的复杂度没分析:迷宫与谜题代码都正确,但最坏情况多慢没量化。

6. 可带走的Copy Anchor Link

1. 递归四步(递归 = 函数自己调用自己):假设函数已存在 → 找基础情况(小到不必再递归的情形)→ 化解为更小同类问题 → 调用假设的函数。
2. 减治解一个更小版(阶乘),分治解多个(斐波那契/汉诺塔);汉诺塔 n 盘 = 2ⁿ−1 步,指数级。
3. 朴素递归斐波那契是指数级(fibo(7) 就要 41 次调用);记忆化让每个值只算一次,变线性。
4. memoize 八行:闭包存缓存、JSON.stringify(把参数序列化成字符串的标准格式)做键、查表优先——可套在任何纯函数上。
5. 记忆化(自顶向下,严格按需)vs 制表(自底向上,可能多做但更快);前缀和 + IIFE = 查询 O(1)。
6. 回溯 = 试错 + || 串联的撤销;「可重复选」的变体只需加一支递归或复制选项。
7. 蛮力属于指数/阶乘级,现实中别用——本书自己就这么宣布;全排列四步算法(Narayana Pandita)留档备用。
8. 贪心每步取当前最优、可能拿不到整体最优:找零看币制,旅行商看运气,最小生成树保证最优。
9. DP 实战不止数列:断行问题的成本定义(空白²)与「超宽即 break」剪枝是可直接搬运的套路。

7. 原文地图Copy Anchor Link