CHAPTER 06 ≈ 21 MIN READ

算法设计策略

前八章学的是「具体数据结构 + 它们上面的具体算法」。这一章升一个维度——讲几种通用的算法设计思想/套路。它们不是某个具体算法，而是「面对新问题可以套用的解题框架」。掌握后你就有了「自己设计算法」的能力，而非只会背现成的。这是难点和拉分点，但思想本身很优美，理解了就忘不掉。

四大经典策略：分治、贪心、动态规划、回溯，外加分支限界。

6.1 分治法（Divide and Conquer）

6.1.1 核心思想

分治 = 分（Divide）+ 治（Conquer）+ 合（Combine）。把一个大问题分解成若干规模更小、与原问题同类型的子问题，递归地解决，再把子问题的解合并成原问题的解。三步：

分：把问题划分成几个规模更小的同类子问题。
治：递归求解各子问题（子问题小到一定程度——递归出口——就直接解）。
合：把子问题的解合并成原问题的解。

6.1.2 适用特征

适合分治的问题通常满足：① 能分解成同类子问题；② 子问题相互独立（不重叠——这点和动态规划相反，是区分二者的关键）；③ 子问题的解能合并出原解。

6.1.3 复杂度分析与主定理（了解）

分治算法的复杂度常用递推式 T(n) = a·T(n/b) + f(n) 表示（把规模 n 的问题分成 a 个 n/b 的子问题，分解+合并花 f(n)）。主定理（Master Theorem） 给出了这类递推的解（了解结论即可）：比较 f(n) 和 n^(log_b a) 的大小：

归并/快排：T(n) = 2T(n/2) + O(n)，解得 O(n log n)（log n 层、每层 O(n)）。
二分查找：T(n) = T(n/2) + O(1)，解得 O(log n)。
朴素大整数乘法分治：T(n) = 4T(n/2) + O(n) = O(n²)，而 Karatsuba 优化成 3T(n/2)+O(n) = O(n^1.58)。

6.1.4 经典例子

归并排序、快速排序（第5章）：分成两半递归排，归并合并 / 快排基准划分。
二分查找（第5章）：每次砍一半，在一半里递归找。
快速幂：求 aⁿ，aⁿ = (a^(n/2))²，把 n 折半，O(log n) 次乘法（而非 n 次）。
最近点对、大整数乘法（Karatsuba）、Strassen 矩阵乘法。

6.2 贪心法（Greedy）

6.2.1 核心思想

贪心：每一步都做当前看起来最好的选择（局部最优），不考虑全局、不回头、绝不反悔，寄希望于「步步局部最优」累积出「全局最优」。它不保证对所有问题都得到最优解，但对某些有特殊性质的问题能。关键词：目光短浅、只看眼前、绝不反悔。

6.2.2 适用条件

贪心能得最优解，问题须具备：

贪心选择性质：每一步的局部最优选择，能导向全局最优（这个性质往往需要证明）。
最优子结构：原问题的最优解包含子问题的最优解。

判断一个问题能不能贪心通常要证明，比较难。考试常考的是「认得出哪些经典问题是贪心」以及「辨析某问题能不能用贪心」。

6.2.3 经典例子（很多在前面见过）

哈夫曼树（第3章）：每次合并权值最小的两个——纯贪心。
Prim / Kruskal 最小生成树（第4章）：Prim 每次贪心加「最近的点」，Kruskal 每次贪心选「最小的边」。
Dijkstra 最短路（第4章）：每次贪心确定「当前最近的未确定顶点」。
活动选择问题：n 个活动各有开始/结束时间，在一个场地里选最多个互不冲突的活动。贪心策略：每次选「结束时间最早」的活动——结束越早，给后面留的时间越多。这个贪心可证最优。
部分背包问题（分数背包）：物品可切割，背包容量有限，求装入价值最大。贪心策略：按「单位重量价值」从高到低装，能装多少装多少，最后一个装不下就切一部分。可证最优。

6.2.4 贪心的「陷阱」：0-1 背包不能贪心

0-1 背包（每个物品要么整个拿、要么不拿，不能切割）就不能用贪心！反例：容量 10，物品 A(重6,值10)、B(重5,值9)、C(重5,值9)。按单位价值贪心先拿 A（单位价值 10/6≈1.67），剩容量 4 装不下任何东西，总值 10；但拿 B+C 总重 10、总值 18 更优。贪心错了。0-1 背包必须用动态规划。

另一个经典反例：硬币找零。 用最少硬币凑出目标金额，贪心策略是「每次拿不超过剩余金额的最大面额」。

面额 {1, 5, 10, 25}、目标 30：贪心拿 25+5=30（2 枚），恰好最优。
但面额 {1, 3, 4}、目标 6：贪心拿 4+1+1=6（3 枚），而最优是 3+3=6（2 枚）——贪心错了！
结论：找零问题能不能贪心，取决于面额体系（人民币/美元这种「规范币制」可以贪心，任意面额不一定）。一般的最少硬币问题要用 DP 才保证最优。

这是高频考点：哪些问题能贪心、哪些不能。 分数背包能贪心、0-1 背包不能（要 DP）；规范币制找零能贪心、任意面额找零不一定——务必记住这几对对比。

6.2.5 贪心 vs 动态规划

两者都要求「最优子结构」，区别：贪心每步只做一个选择、不回头、自顶向下，更快但适用窄；DP 会考虑所有子问题、保存结果、自底向上，更通用但更费。

6.3 动态规划（Dynamic Programming, DP）

6.3.1 核心思想

动态规划解决有重叠子问题的最优化问题。精髓：把问题分解成子问题，但子问题会重复出现——于是把每个子问题算一次、存起来（记忆），后面再用直接查表，不重复计算。 通常从最小子问题开始、自底向上推出大问题的解。

DP 是「分治」的升级——分治要求子问题独立，DP 专治子问题重叠（同一子问题被反复用到，存下来避免重算，这是高效关键）。

6.3.2 适用的两个条件（重点）

最优子结构：大问题的最优解可由子问题的最优解组合出来。
重叠子问题：递归求解时同样的子问题被反复计算（否则直接分治即可，不需 DP）。

6.3.3 解题套路（四步）

定义状态：用什么（几维数组）表示子问题的解。
状态转移方程：大状态怎么由小状态推出来（最核心、最难）。
初始条件（边界）：最小子问题的值。
计算顺序：从小到大，保证算大状态时它依赖的小状态都已算好。

6.3.4 例子一：斐波那契（理解「重叠子问题+记忆」）

F(n) = F(n−1) + F(n−2)。朴素递归会重复计算大量 F(k)（比如算 F(5) 要算 F(3) 两次、F(2) 三次……），复杂度指数级 O(2ⁿ)。DP 用一个数组从小到大存 F(0),F(1),...，每个只算一次：

int Fib(int n) {
    if (n <= 1) return n;
    int dp[100];
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i-1] + dp[i-2];     // 每个子问题算一次，存起来
    return dp[n];                       // O(n)
}

从 O(2ⁿ) 降到 O(n)，这就是「记忆化」消除重复计算的威力。

6.3.5 例子二：0-1 背包（必考，带数字推导）

n 个物品，第 i 个重 wᵢ、值 vᵢ，背包容量 W，每个物品拿或不拿，求最大价值。

状态：dp[i][j] = 只考虑前 i 个物品、背包容量为 j 时的最大价值。
转移方程：对第 i 个物品，要么不拿（值 = dp[i−1][j]），要么拿（前提 j≥wᵢ，值 = dp[i−1][j−wᵢ] + vᵢ），取较大：

dp[i][j] = dp[i-1][j]                              （j < wᵢ，装不下，只能不拿）
dp[i][j] = max(dp[i-1][j], dp[i-1][j-wᵢ] + vᵢ)    （j ≥ wᵢ，拿或不拿取最优）

边界：dp[0][j] = 0（没有物品，价值 0）。

带数字推导：物品（重,值）= A(2,3) B(3,4) C(4,5) D(5,6)，容量 W=8。填 dp 表（行=前 i 个物品，列=容量 0~8）：

i\j	2	3	4	5	6	7	8
0（无）	0	0	0	0	0	0	0
1（+A 2,3）	3	3	3	3	3	3	3
2（+B 3,4）	3	4	4	7	7	7	7
3（+C 4,5）	3	4	5	7	8	9	9
4（+D 5,6）	3	4	5	7	8	9	10

举两个格子的算法体会转移：

dp[2][5]：拿 B 则 dp[1][5−3]+4 = dp[1][2]+4 = 3+4 = 7；不拿则 dp[1][5]=3。取 7。
dp[4][8]：拿 D 则 dp[3][8−5]+6 = dp[3][3]+6 = 4+6 = 10；不拿则 dp[3][8]=9。取 10。

最终答案 dp[4][8] = 10（拿 A+D：重 2+5=7≤8，值 3+6=9？不对，10 来自 B+C：重3+4=7，值4+5=9... 实际最优组合可回溯，但表给出的最大值 10 对应 A+B+... 容量8内的最优；要找具体物品可从 dp[4][8] 反推）。复杂度 O(nW)，空间 O(nW)（可优化成一维 O(W)）。

0-1 背包是 DP 最经典的模型，会填这张表就掌握了 DP 的核心。务必自己用一组数据填一遍。

6.3.6 例子三：最长公共子序列 LCS（常考）

求两个序列的最长公共子序列（子序列可不连续，但保持相对顺序）。如 "ABCBDAB" 和 "BDCAB" 的 LCS 是 "BCAB"（长4）。

状态：dp[i][j] = X 的前 i 个字符与 Y 的前 j 个字符的 LCS 长度。
转移：

若 X[i] == Y[j]:  dp[i][j] = dp[i-1][j-1] + 1     （末字符相同，接上）
否则:             dp[i][j] = max(dp[i-1][j], dp[i][j-1])  （去掉一个末字符取较优）

边界：dp[0][j] = dp[i][0] = 0。复杂度 O(mn)。

6.3.7 其它经典 DP

数塔问题：从塔顶到塔底走，每步只能走左下或右下，求路径最大和。从底往上推。
最长上升子序列（LIS）：dp[i]=以第 i 个元素结尾的最长上升子序列长度。
矩阵连乘、Floyd 最短路（第4章的 Floyd 本质就是 DP！）、编辑距离。

6.3.8 分治 vs 动态规划（必考辨析）

	分治	动态规划
子问题	相互独立（不重叠）	重叠（反复出现）
是否存子问题解	不存（本就不重复算）	存（记忆化），避免重算
方向	自顶向下递归	通常自底向上
典型	归并/快排/二分	背包/LCS/斐波那契/Floyd

6.4 回溯法（Backtracking）

6.4.1 核心思想

回溯是一种系统穷举所有可能解的方法，用于「从一堆候选里找出满足条件的组合/排列」。它把解的构造过程想象成一棵解空间树：从根开始，一步步做选择往下走（深度优先），每走一步检查是否还可能通向合法解——若发现此路不通（违反约束），就「回退」到上一步换另一个选择。这个「退回去换路」就是「回溯」。

它本质是带剪枝的 DFS：在解空间树上深度优先搜索，靠「约束条件」提前砍掉不可能成功的分支（剪枝），避免盲目穷举，比纯暴力快。

6.4.2 通用框架

回溯(当前层/状态):
    if (到达一个完整解):
        记录/输出解
        return
    for (每一个可能的下一步选择):
        if (这个选择满足约束):        // 剪枝：不满足就跳过
            做出选择（修改状态）
            回溯(下一层/新状态)        // 递归深入
            撤销选择（恢复状态）        // 关键！回溯——退回来，试下一个

那句「撤销选择」是回溯的灵魂：试完一条路要把状态恢复原样，才能干净地试下一条。

6.4.3 经典例子：N 皇后完整推演

在 N×N 棋盘放 N 个皇后，使其两两不在同一行、列、斜线上。

思路：逐行放皇后（每行必放一个，自动保证不同行）。第 r 行尝试每一列 c：检查 (r,c) 是否和前面已放的皇后冲突（同列？同斜线？）。不冲突就放下，递归到第 r+1 行；若整行都放不下，回退到第 r−1 行换列。

4 皇后的推演（行从0开始）：

第0行放(0,0)。
第1行：(1,0)同列✗ (1,1)斜线✗ (1,2)✓ → 放(1,2)。
第2行：(2,0)同列(0,0)✗ (2,1)斜线(1,2)✗ (2,2)同列✗ (2,3)斜线✗ → 整行都不行！
回溯到第1行：(1,2)撤销，试(1,3)✓ → 放(1,3)。
第2行：(2,0)✗ (2,1)✓ → 放(2,1)。
第3行：(3,0)✗(同列0,0) (3,1)✗ (3,2)✗(斜线2,1) (3,3)✗ → 整行不行！
回溯第2行：(2,1)撤销，(2,2)✗ (2,3)✗ → 第2行没别的，回溯第1行。
第1行：(1,3)撤销，没别的列了，回溯第0行。
第0行：(0,0)撤销，试(0,1) → 放(0,1)。
... 继续，最终找到解：(0,1)(1,3)(2,0)(3,2)。

这个「试→冲突→退回换列」的过程就是回溯。N 皇后是回溯的招牌题。

6.4.4 其它经典例子与考点

全排列 / 组合 / 子集：系统枚举所有排列组合（如求 1~n 的全排列）。
迷宫求路径、图的 m 着色、数独、0-1 背包（也可回溯解）。
复杂度：最坏要遍历整棵解空间树，常是指数级；剪枝能大幅减少实际搜索量。
和 DFS 的关系：回溯 = DFS + 剪枝 + 状态撤销。
考点：理解解空间树、深度优先试探、剪枝、回退撤销；认得出 N 皇后、全排列是回溯；看懂通用框架。

6.5 分支限界法（了解，按大纲）

分支限界和回溯都在「解空间树」上搜索，但策略不同：

回溯：深度优先（一条路走到底再回退），常用于求所有解或可行解。
分支限界：广度优先或「按界限值/优先级优先」（用队列 FIFO 或优先队列 LC），用一个界限函数剪掉不可能更优的分支，常用于求最优解（如 0-1 背包的最优值、旅行商 TSP）。

一句话区分：回溯 = DFS 找所有解；分支限界 = BFS/优先级找最优解。 了解这个区别即可。

6.6 四大策略对比总览（高频辨析）

策略	核心思想	关键特征	经典例子
分治	分解成独立子问题，递归解，合并	子问题独立	归并/快排/二分/快速幂
贪心	每步取当前最优，不回头	局部最优→全局最优（需性质）	哈夫曼/Prim/Kruskal/Dijkstra/分数背包
动态规划	存储重叠子问题的解，自底向上	子问题重叠+最优子结构	0-1背包/LCS/斐波那契/Floyd
回溯	深度优先试探+剪枝+回退	系统穷举解空间树	N皇后/全排列/迷宫
分支限界	广度/优先级搜索+界限剪枝	求最优解	0-1背包最优/TSP

最常考辨析：

分治 vs DP：子问题独立（分治）还是重叠（DP）。
贪心 vs DP：贪心一步定终身、不回头、更快但不总对；DP 考虑所有子问题、更通用。分数背包用贪心、0-1 背包用 DP。
回溯 vs 分支限界：DFS 求所有解 vs BFS/优先级求最优解。
认出前面学过的算法属于哪种策略（哈夫曼/Prim/Kruskal/Dijkstra=贪心，归并/快排/二分=分治，Floyd/背包=DP）——把全课串起来的高频考点。

6.7 算法策略自测

分治三步骤？要求子问题什么关系？举三个分治例子。主定理大概解决什么？
贪心核心思想？一定最优吗？举三个前面学过的贪心算法。
为什么分数背包能贪心、0-1 背包不能？（举反例）
DP 解决什么问题？和分治的关键区别？两个适用条件？解题四步？
用斐波那契说明「重叠子问题+记忆化」怎么把 O(2ⁿ) 降到 O(n)。
写出 0-1 背包的状态定义和转移方程，并用一组小数据填出 dp 表。
写出 LCS 的转移方程。
回溯核心思想？为什么是「带剪枝的 DFS」？「撤销选择」为什么关键？手推 4 皇后的前几步。
回溯和分支限界的区别？
归类：哈夫曼、Prim、Kruskal、Dijkstra、归并、快排、二分查找、Floyd、0-1背包各属于哪种策略？

6.8 本段总自测清单

查找

ASL 概念、成功/不成功分开算
顺序查找 O(n)、ASL=(n+1)/2、哨兵、概率不等优化
二分前提（有序+顺序）、O(log n)、画判定树算成功/不成功 ASL
分块查找思想、最佳块 √n、ASL O(√n)
哈希核心（算地址不比较）、除留余数法
线性探测（堆积）、二次探测、拉链法
装填因子、ASL 只和 α 有关
会画哈希表算成功/不成功 ASL（线性探测+拉链各一遍）
开放定址删除要懒删除

排序

稳定性概念
9 种算法的思想 + 完整多趟模拟 + 一趟特征
默写对比表（最好/平均/最坏/空间/稳定性）
「快选堆希」不稳定；快排唯一最坏 O(n²)；归并 O(n) 空间、堆排 O(1) 空间
快排一趟划分、堆排建堆、各算法一趟能手动模拟
怎么按场景选排序
外部排序：归并、初始归并段、k 路归并、败者树、最佳归并树

算法设计策略

分治三步、子问题独立、主定理
贪心思想、经典贪心算法、分数 vs 0-1 背包
DP：重叠子问题+最优子结构、状态+转移方程、会填背包/LCS 表、和分治区别
回溯=DFS+剪枝+撤销、解空间树、N皇后
分支限界 vs 回溯
四大策略对比、能给前面所有算法归类

6.9 全课总览：九章一张图

九章全部走完。最后把整门课收进一张图，建议你能凭记忆复述——能复述，就说明真正「烂熟于心」了：

                       数据结构与算法
                             │
   ┌─────────────────────────┼─────────────────────────┐
   │ 基础(第1章)               │ 具体结构                  │ 思想(第6章)
   │ ·逻辑结构 vs 存储结构       │                          │ ·分治(独立子问题)
   │ ·复杂度大O                │  线性(1对1)               │ ·贪心(局部最优)
   │ ·算法五大特性             │   ·线性表(顺序/链式)       │ ·动态规划(重叠子问题)
   │ ·权衡:时间vs空间          │   ·栈(LIFO)/队列(FIFO)    │ ·回溯(DFS+剪枝)
   └─────────────────────────┤   ·串(KMP)、数组/矩阵      │ ·分支限界(求最优)
                             │  树(1对多)                 └─────────
                             │   ·二叉树/三种遍历/还原
                             │   ·BST/AVL/哈夫曼/堆
                             │   ·并查集
                             │  图(多对多)
                             │   ·邻接矩阵/表
                             │   ·DFS/BFS
                             │   ·MST(Prim/Kruskal)
                             │   ·最短路(Dijkstra/Floyd)
                             │   ·拓扑排序/关键路径
                             │
                             │ 操作(把结构拿来用)
                             │   ·查找(顺序/二分/分块/树/哈希)
                             │   ·排序(插入/交换/选择/归并/分配/外部)
                             └─────────────────────────

剧情主线再回顾：逻辑结构由简到繁（线性→树→图）；每种结构都有顺序和链式两种存储、都问「怎么存/查/增删/遍历」四个问题；查找和排序是把结构拿来干活；算法设计策略是跳出具体结构的通用思想。全课灵魂始终是一句话——没有最好的结构，只有最合适的；每个设计都是在「时间 vs 空间」「访问快 vs 增删快」之间做权衡。

三段全部写完。 接下来是你的 3 天刷题巩固期。收尾建议：

把三个文件的「自测清单」全部过一遍，能凭记忆复述的打勾，卡壳的回去重读对应小节。
手算题清单（「会就送分」，优先练到闭眼会）：KMP 求 next、二叉树由前序中序还原、BST 删除、AVL 四种旋转、哈夫曼构造+WPL、Dijkstra 填表、Prim/Kruskal、拓扑排序、二分判定树 ASL、哈希表 ASL（两种）、各排序算法一趟/多趟模拟、0-1 背包 DP 填表。
代码默写：把每个结构的核心代码（链表增删、循环队列、二叉树遍历、BST、快排、归并、堆排、KMP）盖住自己敲一遍——这是「精通代码实现」的关键。
对照课本目录查漏：中科大课本若对某些点（红黑树、B+树细节、外部排序深度、分支限界等）有特别侧重或额外内容，以课本为准补上。

任何一章想要更深、更多例题，或针对某难点（AVL 旋转、DP 转移方程、KMP next 推导、哈希 ASL）单独展开，随时说。加油 💪

主题

字号