算法设计基础考点总结

教材：《算法设计与分析》
适用范围：计算机专业算法课程期末复习
说明：⭐ 标注重要性等级（⭐⭐⭐⭐⭐ 最高）

---

📘 第1章 算法问题求解基础 ⭐⭐⭐

1. 算法的定义与特征 ⭐⭐⭐⭐⭐

算法（Algorithm） 是求解问题的一系列有限步骤。通俗地说，算法就是解决问题的精确方法——它用清晰无歧义的指令序列，告诉你第一步做什么、第二步做什么，直到最终得出结果。

算法 ≠ 程序：算法是设计层面的逻辑步骤，程序是算法在计算机上的具体实现。

算法必须具备以下5个核心特征：

特征	英文	说明	反例
输入	Input	有0个或多个外部输入量	随机数生成器可以无输入
输出	Output	至少产生一个输出量	死循环没有输出，不是算法
确定性	Definiteness	每条指令清晰、无歧义	“选择合适的数据结构”不是确定指令
有限性	Finiteness	对任何合法输入，必须在有限步内结束	操作系统虽然不终止，但不属于算法范畴
可行性	Effectiveness	每条指令都足够基本，可以执行	“列出所有实数”不可行

考试提示：5个特征必须全部记住，尤其区分”确定性”（无歧义）和”有限性”（一定终止于有限步）。

2. 算法设计的基本过程 ⭐⭐⭐

每一步的要点：

1. 理解问题：不仅要读懂题意，还要明确约束条件、输入范围、输出格式
2. 选择策略：这是最核心的决策——判断问题适合用分治、贪心、DP还是回溯
3. 设计算法：先用伪代码描述逻辑，不要急着写具体语言
4. 证明正确性：贪心法必须证明局部最优导致全局最优；归纳法证明递归算法的正确性
5. 分析复杂度：分别分析最坏、平均情况的时间复杂度和空间复杂度
6. 编写代码：注意边界条件、溢出、空指针等细节

3. 递归与归纳证明 ⭐⭐⭐⭐

递归是算法设计中最重要的思维工具之一。其核心思想是：将大问题分解为同类型的、规模更小的子问题。

递归的两个核心要素：

• 递归出口（基值条件 / Base Case）：使递归终止的最简单情况，必须有！
• 递归体（Recursive Case）：将原问题化简为规模更小的同类子问题

递归设计三步走：
① 确定递归函数的含义（它做什么）
② 找出基值条件（什么时候直接求解）
③ 写出递归体（如何用更小规模的子问题表示原问题）

例1：汉诺塔问题（经典递归案例）

问题：三根柱子 A、B、C，n 个大小不同的盘在 A 柱上，每次只能移动一个盘，大盘不能放在小盘上面，求将所有盘移到 C 柱的步骤。

分析思路：
- 若 n=1：直接从 A → C（基值条件）
- 若 n>1：
  ① 先将上面 n-1 个盘从 A → B（递归，借助 C）
  ② 将最大的盘从 A → C（一步完成）
  ③ 将 B 上的 n-1 个盘从 B → C（递归，借助 A）

void Hanoi(int n, char A, char B, char C) {
    if (n == 1)
        cout << A << "→" << C << endl;     // 递归出口
    else {
        Hanoi(n - 1, A, C, B);              // 步骤①：n-1个盘 A→B
        cout << A << "→" << C << endl;      // 步骤②：最大的盘
        Hanoi(n - 1, B, A, C);              // 步骤③：n-1个盘 B→C
    }
}

时间复杂度推导：
$$T(n) = 2T(n-1) + 1,\quad T(1)=1$$
展开得：$T(n) = 2^n - 1 = O(2^n)$

例2：斐波那契数列

// 指数级递归（大量重复计算，n=50就几乎跑不动）
int Fib(int n) {
    if (n <= 1) return n;                    // 基值：F(0)=0, F(1)=1
    return Fib(n-1) + Fib(n-2);              // 递归体
}
// T(n) ≈ O(1.618^n)，非常低效

// 线性迭代（推荐）
int Fib(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b; a = b; b = c;
    }
    return b;
}
// T(n) = O(n)，高效

考试提示：斐波那契递归的重复计算问题是引出动态规划思想的经典案例，期末考试经常以此作为对比。

4. 数学归纳法证明 ⭐⭐⭐

归纳法模板（用于证明递归算法的正确性）：

① 归纳基础：验证 n 取最小值时结论成立
② 归纳假设：假设对于所有 k < n，结论成立
③ 归纳步骤：证明 n 时结论也成立（利用归纳假设）

例：证明汉诺塔算法的最少移动次数为 2^n - 1

• **基础 (n=1)**：移动 1 次 = 2¹-1 = 1，✅ 成立
• 假设：n-1 个盘需要 2^(n-1) - 1 次移动
• 步骤：
  • n-1 个盘 A→B：需要 2^(n-1) - 1 次
  • 最大盘 A→C：需要 1 次
  • n-1 个盘 B→C：需要 2^(n-1) - 1 次
  • 总计 = (2^(n-1) - 1) + 1 + (2^(n-1) - 1) = 2^n - 1 ✅

---

📗 第2章 算法分析基础 ⭐⭐⭐⭐

1. 渐近表示法 ⭐⭐⭐⭐⭐

为什么需要渐近表示法？
算法的实际运行时间取决于机器速度、编译器优化、数据规模等。我们无法精确测量，所以需要用与机器无关的方法来描述算法的效率增长趋势。这就是渐近分析。

渐近表示法关系图：

增长趋势
  ↑
  │  ┌───────────────────  c₂·g(n)（上界）
  │  │  ┌────────────────  c₁·g(n)（下界）
  │  │  │     ╱ f(n)
  │  │  │    ╱
  │  │  │   ╱
  │  │  │  ╱
  │  │  │ ╱
  │  │  │╱
  │──┴──┴─────────────→ n
  │  n₀
  │
  └── Θ(g(n))：f(n)夹在 c₁g(n) 和 c₂g(n) 之间

四种渐近记号对比：

记号	含义	关键不等式	通俗理解	类比
大O $O(g(n))$	渐进上界	$f(n) \le c \cdot g(n)$	$f$ 增长不超过 $g$	$f$ ≤ $g$
大Ω $\Omega(g(n))$	渐进下界	$f(n) \ge c \cdot g(n)$	$f$ 增长至少 $g$ 那么快	$f$ ≥ $g$
大Θ $\Theta(g(n))$	渐进紧确界	$c_1g(n) \le f(n) \le c_2g(n)$	$f$ 和 $g$ 增长同级别	$f$ = $g$
小o $o(g(n))$	非紧上界	$\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$	$f$ 增长严格慢于 $g$	$f$ < $g$

大O证明三步法：

1. 找出候选的 $c$ 和 $n_0$
2. 验证当 $n \ge n_0$ 时，不等式 $f(n) \le c \cdot g(n)$ 成立
3. 写结论

例1：证明 $3n^2 + 2n + 1 = O(n^2)$

解法：需要找到 c 和 n₀，使得 n ≥ n₀ 时 3n²+2n+1 ≤ c·n²

思路：将低阶项放大为 n² 的倍数
      3n² + 2n + 1 ≤ 3n² + 2n² + n² = 6n² （当 n ≥ 1）
      
取 c = 6, n₀ = 1：
当 n ≥ 1 时，3n²+2n+1 ≤ 6n² 恒成立 ✅
∴ 3n² + 2n + 1 = O(n²)

例2：证明 $n^3 \neq O(n^2)$（反证法）

假设 n³ = O(n²)，则存在 c > 0, n₀ 使 n³ ≤ c·n²（∀ n ≥ n₀）
化简得 n ≤ c（∀ n ≥ n₀）
当 n > max(n₀, c) 时矛盾！所以假设不成立 ✅

考试提示：大O证明是必考题！关键技巧是把低阶项”放大”：如 $an^k + bn^{k-1} + … ≤ (|a|+|b|+…)·n^k$（当 $n \ge 1$）。

2. 时间复杂度增长曲线对比 ⭐⭐⭐⭐

n=1      n=10     n=100     n=1000     n=10000
────────────────────────────────────────────────────
O(1)      1        1         1          1          1
O(log n)  0        3.3       6.6        10         13.3
O(n)      1        10        100        1000       10000
O(nlogn)  0        33        664        9966       132877
O(n²)     1        100       10000      10⁶        10⁸
O(n³)     1        1000      10⁶        10⁹        10¹²
O(2ⁿ)     2        1024      1.27e30    ≈∞         ≈∞
O(n!)     1        3.6e6     9.3e157    ≈∞         ≈∞
────────────────────────────────────────────────────

增长速率排名（从慢到快）：

O(1) < O(log n) < O(√n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)

实用结论：$n \le 10^6$ 时 $O(n\log n)$ 秒级可运行，$n \le 10^4$ 时 $O(n^2)$ 勉强可以，$O(2^n)$ 在 $n>30$ 时基本不可行。

3. 递推关系与主方法 ⭐⭐⭐⭐⭐

常见递推式及直觉得解：

类型	递推式	解	直观理解
线性减一	$T(n) = T(n-1) + c$	$O(n)$	每次减1，共n层
减半	$T(n) = T(n/2) + c$	$O(\log n)$	每次减半，共log n层
分治（均衡）	$T(n) = 2T(n/2) + O(n)$	$O(n\log n)$	每层O(n)，共log n层
分治（一般）	$T(n) = aT(n/b) + f(n)$	用主方法	取决于a,b,f(n)

---

主方法（Master Theorem） ⭐⭐⭐⭐⭐

适用范围：$T(n) = aT(n/b) + f(n)$，其中 $a \ge 1, b > 1$

核心思想：比较 $f(n)$（分解+合并代价）与 $n^{\log_b a}$（叶结点代价）

判据：令 E = log_b(a)，即 n^E = n^{log_b a}
     比较 f(n) 与 n^E 的大小关系

情况	条件	结论	本质
情况1：$f(n)$ 更小	$f(n) = O(n^{E-\varepsilon})$	$T(n) = \Theta(n^E)$	叶结点成本主导
情况2：两者相当	$f(n) = \Theta(n^E)$	$T(n) = \Theta(n^E \log n)$	每层均衡
情况3：$f(n)$ 更大	$f(n) = \Omega(n^{E+\varepsilon})$ 且 $af(n/b) \le cf(n)$	$T(n) = \Theta(f(n))$	分解合并成本主导

例题精讲：

题目	a	b	$E=\log_b a$	$f(n)$	判断	答案
$T(n)=9T(n/3)+n$	9	3	$\log_3 9=2$	$n = O(n^{2-1})$	情况1	$\Theta(n^2)$
$T(n)=T(2n/3)+1$	1	3/2	$\log_{3/2}1=0$	$1 = \Theta(n^0)$	情况2	$\Theta(\log n)$
$T(n)=3T(n/4)+n\log n$	3	4	$\log_4 3\approx0.79$	$n\log n = \Omega(n^{0.79+0.2})$	情况3	$\Theta(n\log n)$
$T(n)=2T(n/2)+n\log n$	2	2	$\log_2 2=1$	$n\log n \neq \Theta(n^1)$	主方法不适用	递归树法

考试提示：

1. 主方法前先算 $\log_b a$，写了就给分
2. 找出 $\varepsilon$（哪怕 $\varepsilon=0.01$ 也算数）
3. 情况3必须验证正则条件 $af(n/b) \le cf(n)$（$c<1$）
4. 主方法不能用的时候（情况2不匹配且不属于情况1/3），改用递归树法

4. 递归树法 ⭐⭐⭐

当主方法不适用时（如 $T(n)=T(n/3)+T(2n/3)+O(n)$），用递归树：

                  f(n)=n
            ┌──────┴──────┐
          n/3           2n/3           ← 第1层：n
       ┌──┴──┐        ┌──┴──┐
     n/9   2n/9    2n/9   4n/9         ← 第2层：n
     ...    ...     ...    ...
                                       ← 每层总和 ≤ n
最深路径 ≈ log_{3/2}(n)                ← 沿 2n/3 分支
∴ T(n) = O(n log n)

5. 算法空间复杂度 ⭐⭐

空间类型	来源	是否可优化
固定空间	指令、常量、静态变量	一般不关注
栈空间	递归调用栈	可转为迭代
堆空间	动态分配（数组、结点）	算法决定
总空间	固定空间 + 栈空间 + 堆空间	—

递归栈空间分析：

• 递归深度为 $d$，每次调用占用 $s$ 空间 → 栈空间 = $O(d \cdot s)$
• 例如快排：平均栈深 $O(\log n)$，最坏 $O(n)$

---

📙 第3章 伸展树与跳表 ⭐⭐⭐

1. 伸展树（Splay Tree）⭐⭐⭐⭐

为什么需要伸展树？
AVL树虽然保证了 $O(\log n)$ 的最坏查找时间，但每次插入删除都要维护平衡因子、进行旋转，代码复杂。伸展树另辟蹊径：**不刻意维护”完美平衡”，而是利用”访问局部性”**——最近访问过的结点，下次很可能还会访问。

核心思想：每次访问结点（查找/插入/删除）后，通过一系列旋转操作将该结点 “伸展”到树根位置。这样频繁访问的结点就会聚集在靠近根的位置。

伸展操作（Splay）：

三种旋转情况：

① Zig（单旋转）- 父结点是根：
  访问 x，父 p 是根
      p              x
     / \     →      / \
    x   C          A   p
   / \                / \
  A   B              B   C
  直接对 p 做一次旋转即可

② Zig-Zig（同侧双旋转）- x和父p同侧（都在左或右）：
  先旋转 p（把 p 转上去），再旋转 x（把 x 转上去）
      g              p              x
     / \            / \            / \
    p   D    →     x   g    →     A   p
   / \            / \ / \            / \
  x   C          A  B C  D          B   g
 / \                                   / \
A   B                                 C   D
  关键：先转父(p)，再转子(x)！

③ Zig-Zag（异侧双旋转）- x和父p异侧（一个左一个右）：
  先旋转 x（把 x 转到 p 位置），再旋转 x（把 x 转到 g 位置）
      g              g              x
     / \            / \            / \
    p   D    →     x   D    →     p   g
   / \            / \            / \ / \
  A   x          p   C          A  B C  D
     / \        / \
    B   C      A   B
  关键：对 x 做两次旋转（第一次从子到父，第二次从父到爷）

记忆口诀：

• 父是根 → Zig（一下就够）
• 同侧 → Zig-Zig（先父后子）
• 异侧 → Zig-Zag（子转两次，先到父位再到爷位）

均摊分析：伸展树的单次操作可能达到 $O(n)$，但**均摊时间复杂度为 $O(\log n)$**。这是通过势能分析证明的——每次操作虽然可能花 $O(n)$ 时间，但会让树变得更”平衡”，为后续操作节省时间。

对比表：

操作	AVL树	伸展树
查找	$O(\log n)$ 最坏	$O(\log n)$ 均摊
插入	$O(\log n)$ 最坏	$O(\log n)$ 均摊
删除	$O(\log n)$ 最坏	$O(\log n)$ 均摊
实现难度	复杂	中等
额外空间	O(n) 平衡因子	无需额外空间
访问局部性利用	否	是 ✅

2. 跳表（Skip List）⭐⭐⭐

基本思想：在有序单链表上添加多层索引指针，上层索引跳过大量中间元素，实现类似二分查找的效果。

结构示意：

Level 3:  head ──────────────────→ 30 ──────────────→ null
Level 2:  head ──────→ 10 ──────→ 30 ──────→ 50 ──→ null
Level 1:  head → 5 → 10 → 15 → 20 → 30 → 40 → 50 → null
Level 0:  head → 5 → 10 → 15 → 20 → 25 → 30 → 35 → 40 → 45 → 50 → null
         （完整有序链表）

查找过程（以查找 35 为例）：

① 从最高层(Level 3)开始：head→30→null，30<35，走到30
② 30处下降到Level 2：30→50，50>35，不前进
③ 30处下降到Level 1：30→40，40>35，不前进
④ 30处下降到Level 0：30→35，找到！✅
共走过 4 步（而非 Level 0 从头走的 7 步）

结点提升规则：每个新插入的结点，以概率 $p$（通常 $p=1/2$）决定是否插入到上一层。相当于”抛硬币”决定每层是否保留该结点。

第 i 层期望结点数 = n · p^i
如 n=256, p=1/2：
  Level 0: ~256 个
  Level 1: ~128 个
  Level 2: ~64 个
  ...
  Level 8: ~1 个（根）

期望层数 = log_{1/p}(n) ≈ log₂(n)
每层期望搜索步数 = 1/p = 2（几何分布）
期望总搜索时间 = O(log n)

复杂度总结：

操作	时间复杂度（期望）	最坏情况
查找	$O(\log n)$	$O(n)$（全在Level 0）
插入	$O(\log n)$	$O(n)$
删除	$O(\log n)$	$O(n)$
空间	$O(n)$	$O(n)$（期望1/(1-p)·n）

跳表 vs 平衡树：

特性	跳表	AVL/红黑树
实现复杂度	简单（约100行）	复杂（旋转、染色）
查找性能	$O(\log n)$ 期望	$O(\log n)$ 最坏保证
范围查询	天然支持	需中序遍历
并发友好度	较高	较低（锁整树）
空间开销	稍大（多指针）	较小

考试提示：跳表考概率分析的可能性不大，但要知道基于”随机化”的数据结构思想——用随机性换取实现简单性。

---

📕 第4章 基本搜索和遍历方法 ⭐⭐⭐

1. 深度优先搜索（DFS）⭐⭐⭐⭐⭐

核心策略：一条路走到底，走到死胡同再回头。类似于走迷宫——沿着一条路一直走，碰到墙就退回到最近的岔路口换条路。

// 递归版（最常用）
void DFS(int v) {
    visited[v] = true;         // ① 标记已访问
    cout << v << " ";          // ② 访问当前结点（前序处理）
    for (int w : adj[v])       // ③ 遍历所有邻接点
        if (!visited[w])
            DFS(w);            // ④ 递归深入
}

DFS 执行过程示例：

图：  0──1──3
      │  │
      2  4

DFS(0) 的访问顺序：0 → 1 → 3 → 4 → 2

递归栈变化：
调用DFS(0)：栈=[0]，访问0
  ├─调用DFS(1)：栈=[0,1]，访问1
  │   ├─调用DFS(3)：栈=[0,1,3]，访问3（无未访问邻接点，返回）
  │   └─调用DFS(4)：栈=[0,1,4]，访问4（无未访问邻接点，返回）
  └─调用DFS(2)：栈=[0,2]，访问2（无未访问邻接点，返回）
栈空，遍历结束

DFS 时间复杂度：

• 邻接表：$O(V + E)$ —— 每个顶点访问一次 + 每条边检查一次
• 邻接矩阵：$O(V^2)$ —— 每个顶点需要检查 V 个可能的邻接点

2. 广度优先搜索（BFS）⭐⭐⭐⭐⭐

核心策略：先访问近的，再访问远的。从起点出发，逐层向外扩展——先访问距离为1的结点，再访问距离为2的结点……

void BFS(int s) {
    queue<int> q; q.push(s);
    visited[s] = true;
    
    while (!q.empty()) {
        int v = q.front(); q.pop();
        cout << v << " ";               // ① 出队时访问
        for (int w : adj[v])            // ② 遍历邻接点
            if (!visited[w]) {
                q.push(w);              // ③ 入队
                visited[w] = true;      // ④ 入队即标记（重要！）
            }
    }
}

⚠️ 为什么入队时就标记：如果出队时才标记，同一个结点可能被多次入队，导致重复访问甚至死循环。

BFS 执行过程示例：

图：  0──1──3
      │  │
      2  4

BFS(0) 的访问顺序：0 → 1 → 2 → 3 → 4

队列变化：
初始：q=[0]
出队0：访问0，入队1,2 → q=[1,2]
出队1：访问1，入队3,4 → q=[2,3,4]
出队2：访问2（无未访问邻接点）→ q=[3,4]
出队3：访问3（无未访问邻接点）→ q=[4]
出队4：访问4（无未访问邻接点）→ q=[]
结束

BFS 求无权图最短路径：BFS 按距离递增的顺序访问结点，因此从起点到一个结点第一次被访问时的路径就是最短路径。

void BFS_ShortestPath(int s) {
    vector<int> dist(V, -1);       // dist[i] = 从s到i的距离
    queue<int> q;
    q.push(s); dist[s] = 0;
    
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (int w : adj[v])
            if (dist[w] == -1) {   // 第一次访问
                dist[w] = dist[v] + 1;
                q.push(w);
            }
    }
}

3. DFS 与 BFS 全面对比 ⭐⭐⭐⭐⭐

维度	DFS	BFS
数据结构	栈（递归/显式栈）	队列
搜索策略	纵向优先，一条路走到底	横向优先，逐层扩展
空间复杂度	$O(h)$, $h$ = 树/图的最大深度	$O(w)$, $w$ = 树/图的最大宽度
时间复杂度	$O(V+E)$（邻接表）	$O(V+E)$（邻接表）
适用场景	连通性检测、拓扑排序、回溯法、强连通分量	无权图最短路径、层序遍历、社交网络N度人脉
解的性质	不一定最短	无权图上一定最短
DFS树的边分类	树边、回边、前向边、交叉边	树边、交叉边（无回边和前向边）
递归实现	自然、简洁	不自然，用队列迭代
栈空间风险	深度大时可能栈溢出	宽度大时内存占用多

考试提示：DFS的四类边是理解很多图算法的基础，必须掌握。

4. DFS 边的分类 ⭐⭐⭐

在有向图 DFS 树中：

树边(Tree Edge)：     DFS树中的边，v是w的父结点
回边(Back Edge)：     指向祖先结点的边  → 意味着存在环路！
前向边(Forward Edge)： 指向后代（非直接子结点）的边
交叉边(Cross Edge)：   连接不同子树或不同DFS树的边

       0 (d=1, f=10)
      / \
 (2,7)1   2 (8,9)      树边：0→1, 0→2, 1→3
    / \                 回边：3→1（指向祖先）
(3,4)3  4 (5,6)         前向边：0→4（指向后代，非直接子结点）
        ↑               交叉边：4→2（不同子树之间）
        0

5. 括号定理 ⭐⭐⭐

在 DFS 遍历中，每个结点 $v$ 有两个时间戳：

• 发现时间 $d[v]$：$v$ 首次被访问（着色为灰色）
• 完成时间 $f[v]$：$v$ 的所有后继访问完毕（着色为黑色）

括号定理：对于任意两个结点 $u$ 和 $v$，它们的区间 $[d[u], f[u]]$ 和 $[d[v], f[v]]$ 满足以下三者之一：

1. 完全分离：$f[u] < d[v]$ 或 $f[v] < d[u]$（$u$ 和 $v$ 不在同一DFS树分支中）
2. 完全嵌套：$[d[v], f[v]] \subset [d[u], f[u]]$（$v$ 是 $u$ 的后代）
3. 完全嵌套：$[d[u], f[u]] \subset [d[v], f[v]]$（$u$ 是 $v$ 的后代）

不可能出现“部分重叠”的情况！这正是”括号”名称的由来。

推论：$v$ 是 $u$ 的后代当且仅当 $d[u] < d[v] < f[v] < f[u]$

6. 双连通分量与关节点 ⭐⭐⭐

关节点（Articulation Point）：删除后导致图不再连通的顶点。

图：  A──B──C
      │  │
      D  E

关节点：B（删除后图分裂为 {A,D}, {C}, {E}）
非关节点：A, C, D, E

利用 DFS 求关节点：

定义两个数组：

• dfn[v]：DFS 访问编号（深度优先数）
• low[v]：从 $v$ 出发，通过最多一条回边能到达的最小 dfn

判定条件：

• 根结点：若 DFS 树中根有两个或更多孩子 → 根是关节点
• 非根结点 $v$：若存在孩子 $w$ 使得 $low[w] \ge dfn[v]$ → $v$ 是关节点（意味着 $w$ 及其后代无法绕过 $v$ 到达 $v$ 的祖先）

---

📓 第5章 分治法 ⭐⭐⭐⭐

1. 分治法基本思想 ⭐⭐⭐⭐⭐

分治法（Divide and Conquer） 是算法设计中最经典的策略之一。核心思路非常简单：大问题不好解决，就把它拆成小问题，各个击破，再合并答案。

     原问题（规模 n）
     ╱            ╲
子问题1(规模n/2)  子问题2(规模n/2)    ← Divide（分解）
   ╱    ╲          ╱    ╲
 ...    ...      ...    ...         ← 递归求解
   ╲    ╱          ╲    ╱
   子解1            子解2             ← Conquer（求解）
     ╲            ╱
      合并（Combine）                  ← Combine（合并）
          ↓
       最终解

分治法适用条件：

1. 问题规模缩小到一定程度可以容易地直接求解
2. 问题可以分解为若干规模较小的相同问题（最优子结构）
3. 子问题的解可以合并为原问题的解
4. 子问题之间相互独立（与 DP 的关键区别）

2. 二分搜索 ⭐⭐⭐⭐

问题：在已排序的数组 $a[0..n-1]$ 中查找值为 $x$ 的元素。

int BinarySearch(int a[], int n, int x) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;  // 防溢出写法
        if (a[mid] == x) return mid;
        else if (a[mid] < x) left = mid + 1;
        else right = mid - 1;
    }
    return -1;  // 未找到
}

示例：在 [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] 中查找 23

Step 1: left=0, right=9, mid=4, a[4]=16 < 23 → left=5
Step 2: left=5, right=9, mid=7, a[7]=56 > 23 → right=6
Step 3: left=5, right=6, mid=5, a[5]=23 == 23 → 找到！✅

递推方程：$T(n) = T(n/2) + O(1)$，解得 $T(n) = O(\log n)$

3. 归并排序 ⭐⭐⭐⭐⭐

思想：将数组二分，分别排序，然后合并两个有序子数组。精髓在**合并(Merge)**操作。

void Merge(int a[], int left, int mid, int right) {
    int n1 = mid - left + 1, n2 = right - mid;
    int *L = new int[n1], *R = new int[n2];
    for (int i = 0; i < n1; i++) L[i] = a[left + i];
    for (int i = 0; i < n2; i++) R[i] = a[mid + 1 + i];
    
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2)
        a[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
    while (i < n1) a[k++] = L[i++];
    while (j < n2) a[k++] = R[j++];
    delete[] L; delete[] R;
}

void MergeSort(int a[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        MergeSort(a, left, mid);
        MergeSort(a, mid + 1, right);
        Merge(a, left, mid, right);
    }
}

分治过程示意：

              [38,27,43,3,9,82,10]
              ╱                  ╲
      [38,27,43,3]            [9,82,10]
      ╱         ╲             ╱      ╲
  [38,27]      [43,3]      [9,82]   [10]
  ╱    ╲       ╱   ╲      ╱   ╲
[38]  [27]   [43] [3]   [9]  [82]
  ╲    ╱       ╲   ╱      ╲   ╱
  [27,38]     [3,43]     [9,82]
      ╲         ╱             ╲      ╱
      [3,27,38,43]            [9,10,82]
              ╲                  ╱
              [3,9,10,27,38,43,82]

• 时间复杂度：$T(n) = 2T(n/2) + O(n)$，主方法情况2 → $O(n\log n)$
• 空间复杂度：$O(n)$（需要辅助数组）
• 稳定排序：相等元素的相对顺序不变

4. 快速排序 ⭐⭐⭐⭐⭐

思想：选一个基准元素(pivot)，将数组划分为”小于pivot”和”大于pivot”两部分，再递归排序两部分。

int Partition(int a[], int left, int right) {
    int pivot = a[left];          // 选择第一个元素作为基准
    while (left < right) {
        // 从右向左找第一个小于pivot的元素
        while (left < right && a[right] >= pivot) right--;
        a[left] = a[right];       // 将该元素移到左边
        // 从左向右找第一个大于pivot的元素
        while (left < right && a[left] <= pivot) left++;
        a[right] = a[left];       // 将该元素移到右边
    }
    a[left] = pivot;              // 基准归位
    return left;
}

划分过程详解（以 [38, 27, 43, 3, 9, 82, 10] 为例，pivot=38）：

初始:  [38, 27, 43, 3, 9, 82, 10]  left=0(pivot=38), right=6

① right=6, a[6]=10<38 → a[0]=10 → [10, 27, 43, 3, 9, 82, 10]
   left=1, a[1]=27<38 → left=2, a[2]=43>38 → a[6]=43 → [10, 27, 43, 3, 9, 82, 43]

② right=5, a[5]=82>38 → right=4, a[4]=9<38 → a[2]=9 → [10, 27, 9, 3, 9, 82, 43]
   left=3, a[3]=3<38 → left=4

③ left=4, right=4 → 出循环, a[4]=38
   结果: [10, 27, 9, 3, |38|, 82, 43]
        ← 小于38 →          ← 大于38 →

快排性能分析：

情况	条件	递推式	时间复杂度
最好/平均	每次均匀划分	$T(n)=2T(n/2)+O(n)$	$O(n\log n)$
最坏	每次分出一个空集	$T(n)=T(n-1)+O(n)$	$O(n^2)$（退化为选择排序）

**何时退化为 $O(n^2)$**：

• 数组已经有序（或逆序），且选第一个/最后一个元素为 pivot
• 数组所有元素相等（如果用 <= 和 >= 划分）

改进方案：

• 随机选 pivot（期望 $O(n\log n)$）
• 三数取中法（median-of-three）
• 小数组切换为插入排序

考试提示：快排的划分过程(PARTITION)是考试最高频代码之一，必须能手写。退化条件的理解也很重要。

5. 分治法求最大最小元 ⭐⭐⭐

问题：在数组中找到最大值和最小值，尽量减少比较次数。

朴素做法：分别找最大值(n-1次)和最小值(n-1次) → $2n-2$ 次比较

分治做法：

① 二分数组为两半
② 递归求左半的 (maxL, minL) 和右半的 (maxR, minR)
③ 合并：max = max(maxL, maxR)，min = min(minL, minR)

递推式：$T(n) = 2T(n/2) + 2$，解得 $T(n) = \frac{3n}{2} - 2$，比 $2n-2$ 少约 25%。

6. Strassen 矩阵乘法 ⭐⭐

问题：计算两个 $n \times n$ 矩阵的乘积。

普通算法：$O(n^3)$（三重循环）

Strassen 的巧妙之处：将8次 $n/2 \times n/2$ 乘法减少为 7次！

递推式：T(n) = 7T(n/2) + O(n²)
主方法：a=7, b=2, log₂7≈2.81
      f(n)=O(n²)=O(n^{2.81-0.81}) → 情况1
T(n) = Θ(n^{log₂7}) ≈ Θ(n^{2.81})

虽然理论上优于 $O(n^3)$，但由于常数因子大，实际应用仍以优化后的传统算法为主。

---

📒 第6章 贪心法 ⭐⭐⭐⭐⭐

1. 贪心法核心思想 ⭐⭐⭐⭐⭐

贪心法（Greedy Method）是求解最优化问题的一种策略。它的哲学很简单：每一步都做当前看起来最好的选择，相信这些局部最优选择最终会拼出全局最优解。

贪心法不像 DP 那样"瞻前顾后"，它就盯着眼前这一步的最大利益。
有点像下棋时每步都选当前价值最高的落子——不一定赢全盘，但有时偏偏就是最优策略。

贪心法算法模板：

SolutionType Greedy(SType a[], int n) {
    SolutionType solution = ∅;           // 空解
    for (int i = 0; i < n; i++) {
        SType x = Select(a);            // ① 按贪心准则选择下一个分量
        if (Feasible(solution, x))      // ② 可行解判定
            solution = Union(solution, x); // ③ 合并到解中
    }
    return solution;
}

贪心法两大关键要素：

要素	含义	为什么重要
最优量度标准	每一步选择的依据（如选性价比最高的物品）	选错了准则 → 得不到最优解
最优子结构	最优解包含子问题的最优解	是贪心法能用的前提条件

⚠️ 重要提醒：贪心法不总是能得到全局最优解！使用贪心法之前必须证明量度标准的正确性。如果无法证明，就不能保证答案是最优的。

2. 背包问题 ⭐⭐⭐⭐⭐

一般背包问题（物品可分割）

贪心策略：按单位重量收益 $p_i/w_i$ 从大到小排序，优先装性价比最高的物品。

示例：M=20, (w₀,w₁,w₂)=(18,15,10), (p₀,p₁,p₂)=(25,24,15)

计算性价比：
  物品0: 25/18 ≈ 1.39
  物品1: 24/15 = 1.60  ← 最高！
  物品2: 15/10 = 1.50

按性价比排序：物品1(1.60) > 物品2(1.50) > 物品0(1.39)

决策过程：
① 先装物品1(重15)：x₁=1.0, 剩余容量=5, 收益=24
② 装物品2(重10)：x₂=5/10=0.5, 剩余容量=0, 收益=24+7.5=31.5
③ 背包装满，结束

最优解：X=(0, 1, 0.5)，总收益=31.5

void GreedyKnapsack(float *x) {
    // 前置条件：物品已按 p[i]/w[i] 非增排序
    float u = M;                   // 剩余容量
    for (int i = 0; i < n; i++)
        x[i] = 0;                  // 初始化
    for (int i = 0; i < n; i++) {
        if (w[i] > u) break;       // 整件放不下
        x[i] = 1.0;                // 整件放入
        u -= w[i];
    }
    if (i < n) x[i] = u / w[i];    // 最后一件放一部分
}

时间复杂度：$O(n\log n)$（排序主导）

0/1背包问题（物品不可分割）

贪心法不能保证得到0/1背包的最优解！

反例：M=50, 三件物品
  物品0: w=10, p=60  (性价比 6.0)
  物品1: w=20, p=100 (性价比 5.0)
  物品2: w=30, p=120 (性价比 4.0)

贪心解（按性价比）：选0+1 = 收益160
最优解（DP）：     选1+2 = 收益220  ← 更好！

为什么贪心会出错？ 因为0/1背包的选择有”排他性”——选了高性价比的小物品可能挤占容量，导致无法装入虽性价比略低但总价值更高的大物品。

3. 带时限的作业排序 ⭐⭐⭐⭐

问题：$n$ 个作业，每个运行 1 单位时间，截止期限 $d_i$，收益 $p_i$（按降序排列）。选一个子集使得都能在期限内完成且总收益最大。

核心技巧：每个作业尽可能安排在靠后的时间片（越靠后越难安排，给前面的作业留出空间）。

例：n=4, d=(2,1,2,1), p=(100,10,15,27)（已按收益降序）

决策过程：
① 作业0(p=100, d=2)：安排在时间2 → J={0}
② 作业1(p=10,  d=1)：安排在时间1 → J={0,1}
③ 作业2(p=15,  d=2)：时间2已被占，时间1也被占 → 无法安排
④ 作业3(p=27,  d=1)：时间1已被占 → 无法安排

最优解：J={0,1}，总收益=110

int JS(int *d, int *x, int n) {
    // 前置：p₀ ≥ p₁ ≥ … ≥ p_{n-1}
    int k = 0; x[0] = 0;           // 选中作业0
    for (int j = 1; j < n; j++) {  // 依次考察其余作业
        int r = k;
        // 找到插入位置：按时限非减且不超期
        while (r >= 0 && d[x[r]] > d[j] && d[x[r]] > r + 1)
            r--;
        if ((r < 0 || d[x[r]] <= d[j]) && d[j] > r + 1) {
            // 插入j到位置r+1
            for (int i = k; i >= r + 1; i--) x[i+1] = x[i];
            x[r + 1] = j; k++;
        }
    }
    return k + 1;                   // 返回选中作业数
}

时间复杂度：$O(n^2)$

并查集优化版（FJS）：用并查集快速找到离截止时间最近的空闲时间片，时间复杂度接近 $O(n)$。

4. 最佳合并模式 = 哈夫曼树 ⭐⭐⭐⭐

问题：合并 $n$ 个长度不同的有序文件，每次合并两个文件的成本是两文件长度之和，求使总成本最小的合并顺序。

这其实就是哈夫曼编码问题的变体！

例：文件长度分别为 5, 10, 20, 30, 30

构造过程（每次选两个最小的合并）：
Step 1: min=5,10 → 合并得15，现在有 {15, 20, 30, 30}
Step 2: min=15,20 → 合并得35，现在有 {30, 30, 35}
Step 3: min=30,30 → 合并得60，现在有 {35, 60}
Step 4: min=35,60 → 合并得95

哈夫曼树：
          95
        ╱    ╲
      35      60
     ╱ ╲    ╱  ╲
   15   20 30   30
  ╱ ╲
 5   10

WPL = 5×3 + 10×3 + 20×2 + 30×2 + 30×2 = 15+30+40+60+60 = 205

K路合并：推广为 K 路合并（每次合并 K 个文件），需要补充 虚结点（零权值）：

• 补充数 = $(K-1) - (n-1)%(K-1)$ 个
• 例如 n=8, K=3：$(3-1) - (8-1)%(3-1) = 2-1 = 1$ 个虚结点

5. 最小代价生成树（MST）⭐⭐⭐⭐⭐

Prim 算法：从一个顶点开始，每次选一条连接树内外的最小边。

示例图（邻接矩阵）：
      0 --1-- 1
      | \   / |
      5  2  5 3
      |   \   |
      2 --4-- 3
      |       |
      6       2
      4-------5

Prim(0) 过程：
初始：S={0}, nearest=[-1,-1,-1,-1,-1], lowcost=[∞,∞,∞,∞,∞]

选0作为起点(根)：
  nearest=[0,0,0,0,0], lowcost=[0,1,5,∞,∞]
  ↑ lowcost[0]=0 (已在S中)

Step 1: 选最小lowcost未标记 → 结点1(lowcost=1)
  S={0,1}, 更新1的邻接：结点4(lowcost[4]=3)
  nearest=[0,0,0,1,0], lowcost=[0,1,5,3,∞]

Step 2: 选最小 → 结点4(lowcost=3)
  S={0,1,4}, 更新4的邻接：结点3(lowcost[3]=2)
  nearest=[0,0,4,1,0], lowcost=[0,1,5,2,∞]

Step 3: 选最小 → 结点3(lowcost=2)
  S={0,1,4,3}, 更新3的邻接：结点2(lowcost[2]=4)
  nearest=[0,0,3,1,0], lowcost=[0,1,4,2,∞]

Step 4: 选最小 → 结点2(lowcost=4)
  S={0,1,4,3,2}, 更新2的邻接：(无变化)

MST边集：(0,1,1) (1,4,3) (4,3,2) (3,2,4)
总代价 = 1+3+2+4 = 10

Kruskal 算法：按边权从小到大选边，不形成回路即可。

同样上图，边按权值排序：
(0,1,1), (1,4,3), (0,2,5), (4,3,2), (1,2,5), (3,2,4)...

① 选(0,1,1)：集合{0,1}
② 选(1,4,3)：集合{0,1,4}
③ 选(4,3,2)：集合{0,1,3,4}
④ 选(0,2,5)：集合{0,1,2,3,4}
... 已选4条边=n-1，结束

MST边集同Prim结果，总代价=1+3+2+5=11? ← No! 应该是...

Prim vs Kruskal 对比：

维度	Prim	Kruskal
策略	结点扩展	边扩展
数据结构	nearest[], lowcost[]	并查集 + 优先权队列
时间复杂度	$O(V^2)$（邻接矩阵）	$O(E\log E)$
堆优化	$O(E\log V)$	—
适合场景	稠密图（$E\approx V^2$）	稀疏图（$E\approx V$）

考试提示：MST是图论的绝对核心考点！手工模拟 Prim 和 Kruskal 都要熟练掌握。MST性质的证明思路要清楚。

6. 迪杰斯特拉（Dijkstra）最短路径 ⭐⭐⭐⭐⭐

Dijkstra 算法求单源最短路径（非负权有向图）。

数据结构：

• d[i]：源点到 $i$ 的当前最短距离
• path[i]：最短路径上 $i$ 的前驱结点（用于回溯路径）
• inS[i]：是否已确定最短路径

Dijkstra 手工模拟示例：

图（邻接矩阵，INF表示无边）：
    0   1   2   3   4
0   0   10  INF  30  100
1  INF  0   50  INF INF
2  INF INF  0  INF  10
3  INF INF  20   0   60
4  INF INF INF INF   0

源点 s=0

初始化：
d[]  = [0, 10, INF, 30, 100]
path[]=[-1, 0, -1, 0, 0]
inS[]=[T, F, F, F, F]

Step 1: 选 d 最小的未选结点 → 1(d=10)
  S={0,1}，以1为中介松弛：
  d[0]+w(1,2)=10+50=60 < INF → d[2]=60, path[2]=1
  
  d[]  = [0, 10, 60, 30, 100]
  path[]=[-1, 0, 1, 0, 0]

Step 2: 选 d 最小的 → 3(d=30)
  S={0,1,3}，松弛：
  d[3]+w(3,2)=30+20=50 < 60 → d[2]=50, path[2]=3
  d[3]+w(3,4)=30+60=90 < 100 → d[4]=90, path[4]=3
  
  d[]  = [0, 10, 50, 30, 90]
  path[]=[-1, 0, 3, 0, 3]

Step 3: 选 d 最小的 → 2(d=50)
  S={0,1,3,2}，松弛：
  d[2]+w(2,4)=50+10=60 < 90 → d[4]=60, path[4]=2
  
  d[]  = [0, 10, 50, 30, 60]
  path[]=[-1, 0, 3, 0, 2]

Step 4: 选 d 最小的 → 4(d=60)
  S={0,1,3,2,4}，全完成

最终最短距离：d=[0, 10, 50, 30, 60]
最短路径回溯：
  0→1: [0→1] = 10
  0→2: [0→3→2] = 50
  0→3: [0→3] = 30
  0→4: [0→3→2→4] = 60

⚠️ Dijkstra 适用条件：所有边权必须非负！有负权边时需用 Bellman-Ford 算法。

7. 贪心法证明方法论 ⭐⭐⭐⭐

方法	核心思路	适用场景
归纳法	证明第一步贪心选择不会丢掉最优解，然后对剩余问题归纳	MST、最佳合并模式
交换论证	假设最优解与贪心解不同，通过交换元素证明贪心解不差	背包、作业排序
反证法	假设贪心解不是最优，导出矛盾	Dijkstra、MST性质

交换论证模板（以背包问题为例）：

① 假设贪心解G不是最优，则存在最优解O ≠ G
② 设k是G和O第一个不同的位置
③ 由于贪心按p/w降序选择，G[k]必定≥O[k]
④ 构造新解O'：将O的第k个分量调整为G[k]，去掉后面多余部分
⑤ 可证 O' 的收益 ≥ O的收益
⑥ 重复此过程将O完全变为G
⑦ 所以G也是最优解（矛盾于假设）

---

📔 第7章 动态规划法 ⭐⭐⭐⭐⭐

1. 动态规划核心思想 ⭐⭐⭐⭐⭐

动态规划（Dynamic Programming）解决的是具有重叠子问题的最优化问题。

DP vs 分治法 vs 贪心法：

	分治法	贪心法	动态规划
子问题关系	独立	—	重叠 ✅
求解方向	自顶向下	自顶向下（逐步）	自底向上 ✅
存储子解	不需要	不需要	需要（记忆化） ✅
最优子结构	有	有	有
保证最优？	—	不一定（需证明）	一定 ✅

DP 四步法：

① 刻画最优解的结构特征   ← 什么是一个"状态"？
② 递归定义最优解的值     ← 写出DP方程
③ 自底向上计算最优值     ← 填表
④ 根据信息构造最优解     ← 回溯

2. 最长公共子序列（LCS）⭐⭐⭐⭐⭐

问题：给定两个序列 X 和 Y，求它们的最长公共子序列。

子序列 ≠ 子串：子序列不要求连续，子串要求连续。
例如 X=”abcdefg”，”aceg” 是子序列但不是子串。

DP 方程：

$$dp[i][j] = \begin{cases} 0 & i=0 \text{ 或 } j=0 \ dp[i-1][j-1] + 1 & X[i] = Y[j] \ \max(dp[i-1][j], dp[i][j-1]) & X[i] \neq Y[j] \end{cases}$$

LCS 手工填表演示（$X=ABCBDAB$, $Y=BDCABA$）：

     ""  B   D   C   A   B   A
   ┌───┬───┬───┬───┬───┬───┬───┐
"" │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │
   ├───┼───┼───┼───┼───┼───┼───┤
A  │ 0 │ 0 │ 0 │ 0 │ 1 │ 1 │ 1 │
   ├───┼───┼───┼───┼───┼───┼───┤
B  │ 0 │ 1 │ 1 │ 1 │ 1 │ 2 │ 2 │
   ├───┼───┼───┼───┼───┼───┼───┤
C  │ 0 │ 1 │ 1 │ 2 │ 2 │ 2 │ 2 │
   ├───┼───┼───┼───┼───┼───┼───┤
B  │ 0 │ 1 │ 1 │ 2 │ 2 │ 3 │ 3 │
   ├───┼───┼───┼───┼───┼───┼───┤
D  │ 0 │ 1 │ 2 │ 2 │ 2 │ 3 │ 3 │
   ├───┼───┼───┼───┼───┼───┼───┤
A  │ 0 │ 1 │ 2 │ 2 │ 3 │ 3 │ 4 │
   ├───┼───┼───┼───┼───┼───┼───┤
B  │ 0 │ 1 │ 2 │ 2 │ 3 │ 4 │ 4 │
   └───┴───┴───┴───┴───┴───┴───┘

回溯构造 LCS（从右下角 dp[7][6]=4 开始）：

dp[7][6]=4（不同），← ← dp[7][5]=4（相同！X[7]=B=Y[5]）→ 选B
dp[6][4]=3（不同），← ← dp[6][3]=3（相同！X[6]=A=Y[4]）→ 选A
dp[5][2]=2（不同），← 上 dp[4][2]=2（不同），← dp[4][1]=2（相同！X[4]=B=Y[2]？不），检查...
最终 LCS = "BCBA" 或 "BDAB"

考试提示：LCS 填表 + 回溯必须熟练掌握，期末考试手算常考！

3. 矩阵连乘问题 ⭐⭐⭐⭐

问题：矩阵乘法满足结合律但不满足交换律。不同的加括号方式导致不同的乘法次数。求最优加括号方案使总乘法次数最少。

问题建模：设 $n$ 个矩阵 $A_1 \times A_2 \times … \times A_n$，$A_i$ 的维数为 $p_{i-1} \times p_i$

DP 方程：

$$m[i][j] = \begin{cases} 0 & i=j \ \min\limits_{i \le k < j}{m[i][k] + m[k+1][j] + p_{i-1}p_k p_j} & i < j \end{cases}$$

手工填表示例（$p=[30,35,15,5,10,20]$，即 5 个矩阵）：

对角线上 m[i][i]=0：
      A1    A₂    A₃    A₄    A₅
     30×35 35×15 15×5  5×10  10×20
    ┌─────┬─────┬─────┬─────┬─────┐
 A1 │  0  │     │     │     │     │
    ├─────┼─────┼─────┼─────┼─────┤
 A₂ │  -  │  0  │     │     │     │
    ├─────┼─────┼─────┼─────┼─────┤
 A₃ │  -  │  -  │  0  │     │     │
    ├─────┼─────┼─────┼─────┼─────┤
 A₄ │  -  │  -  │  -  │  0  │     │
    ├─────┼─────┼─────┼─────┼─────┤
 A₅ │  -  │  -  │  -  │  -  │  0  │
    └─────┴─────┴─────┴─────┴─────┘

计算 m[1][2]（链长2）：k=1，30×35×15=15750
计算 m[2][3]：k=2，35×15×5=2625
...
最终 m[1][5] = 11875（最优乘法次数）
s[1][5] = 3（最优分割点在k=3）

考试提示：要理解为什么按对角线方向填表——因为计算 $m[i][j]$ 需要依赖 $m[i][k]$ 和 $m[k+1][j]$（$i \le k < j$），必须保证子问题先求解。

4. 0/1背包问题 ⭐⭐⭐⭐⭐

DP 方程：

$$dp[i][j] = \begin{cases} dp[i-1][j] & w_i > j \text{（装不下，不选）} \ \max(dp[i-1][j],; dp[i-1][j-w_i] + p_i) & w_i \le j \text{（选或不选取大）} \end{cases}$$

手工填表示例（$M=10$, $(w,p)=[(2,6),(2,3),(6,5),(5,4),(4,6)]$）：

物品\容量  0  1  2  3  4  5  6  7  8  9  10
────────────────────────────────────────────────
  0(空)    0  0  0  0  0  0  0  0  0  0  0
  1(2,6)   0  0  6  6  6  6  6  6  6  6  6
  2(2,3)   0  0  6  6  9  9  9  9  9  9  9
  3(6,5)   0  0  6  6  9  9  9  9 11 11 14
  4(5,4)   0  0  6  6  9  9  9 10 11 13 14
  5(4,6)   0  0  6  6  9  9 12 12 15 15 15
                                  ↑ 最优值=15

一维优化（常见考试写法）：

for (int i = 1; i <= n; i++)
    for (int j = M; j >= w[i]; j--)   // ⚠️ 必须逆序！
        dp[j] = max(dp[j], dp[j - w[i]] + p[i]);

为什么会错如果正序？ 因为 $dp[j-w[i]]$ 可能已经被当前物品更新过，导致同一物品被多次选取（变成完全背包）。

5. 最优二叉搜索树（OBST）⭐⭐⭐

问题：给定键 $k_1<k_2<…<k_n$ 的查找概率 $p_i$ 和虚键 $d_0<d_1<…<d_n$ 的概率 $q_j$，构造期望搜索代价最小的 BST。

DP 方程：

$$w(i,j) = w(i,j-1) + p_j + q_j$$
$$c(i,j) = \min_{i < k \le j}{c(i,k-1) + c(k,j)} + w(i,j)$$

$w(i,j)$ 是子树包含的所有概率之和（该子树增加一层，期望代价增加 $w(i,j)$）。

6. 多段图问题 ⭐⭐⭐

问题：将图分为 $k$ 个阶段，边只能从前一阶段指向后一阶段，求源点到终点的最短路径。

DP 从后往前推：

阶段4  阶段3    阶段2    阶段1    阶段0
(t)    (8,9)   (5,6,7)  (2,3,4)   (s)

dp[t] = 0（终点）
dp[8] = min{cost(8,t)+dp[t]} = 3
dp[9] = min{cost(9,t)+dp[t]} = 4
dp[5] = min{cost(5,8)+dp[8], cost(5,9)+dp[9]} = min{1+3, 4+4} = 4
...

7. DP 问题对比总表 ⭐⭐⭐⭐⭐

问题	状态定义	递推方向	时间	空间	构造最优解
多段图	dp[i]=i到终点最短距离	后→前	$O(V+E)$	$O(V)$	path[i]
矩阵连乘	$m[i][j]$=Ai..Aj最小乘法数	对角线	$O(n^3)$	$O(n^2)$	s[i][j]
LCS	$dp[i][j]$=X[1..i]与Y[1..j]的LCS长度	行→下	$O(mn)$	$O(mn)$	箭头回溯
OBST	$c(i,j)$=子树最小代价	对角线	$O(n^3)$	$O(n^2)$	r(i,j)
0/1背包	$dp[i][j]$=前i件容量j的最大价值	行→下	$O(nM)$	$O(M)$	回溯判断

考试提示：DP 题三步走——①写方程 → ②填表 → ③回溯，三步都有分，跳步就丢分！

---

📚 第8章 回溯法 ⭐⭐⭐⭐

1. 回溯法核心思想 ⭐⭐⭐⭐⭐

回溯法 = 深度优先搜索 + 剪枝

回溯法系统地搜索解空间树。它与暴力枚举（穷举法）的根本区别在于：
当发现当前的部分解不可能扩展为完整解时，立即停止搜索该分支（剪枝），回到上层尝试其他选择。

解空间树两种类型：

子集树（每个元素选或不选）：         排列树（n个元素的各种排列）：
            {}                              [1,2,3]
         ╱      ╲                     ╱       │       ╲
      选0      不选0            1开头       2开头      3开头
     ╱  ╲     ╱  ╲            [1,2,3]     [2,1,3]    [3,1,2]
   选1 不选1 选1 不选1        ╱    ╲       ╱    ╲      ╱    ╲
   ...                       2和3互换...  1和3互换... 1和2互换...

叶结点数：2ⁿ                    叶结点数：n!
适用：0/1背包、子集和          适用：n皇后、TSP

2. n皇后问题 ⭐⭐⭐⭐⭐

关键约束：任意两个皇后不能在同一行、同一列、同一对角线。

棋盘编号（4皇后为例）：
列：   1   2   3   4
行1：  Q   ·   ·   ·
行2：  ·   ·   Q   ·
行3：  ·   ·   ·   ·
行4：  ·   ·   ·   ·

解：x[1]=1, x[2]=3, x[3]=?, x[4]=?
  （x[i]=j 表示第i行的皇后放在第j列）

约束检查函数（Place）：

bool Place(int k, int i) {
    // 判断第k行的皇后能否放在第i列
    for (int j = 1; j < k; j++) {
        // 条件1：不同列 → x[j] == i
        if (x[j] == i) return false;
        // 条件2：不同对角线 → |行差| == |列差|
        if (abs(x[j] - i) == abs(j - k)) return false;
    }
    return true;
}

对角线判断：abs(x[j]-i) == abs(j-k) 是核心公式！两个位置在同一对角线上当且仅当行差等于列差。

4皇后解空间树部分剪枝示意：

                   root
         ┌─────┬────┼────┬─────┐
        x1=1  x1=2 x1=3 x1=4
         │
       x2=3  (x2=1,2,4都被约束剪掉：同列或同对角线)
         │
       x3=?  (x3=1,2,3,4全被剪掉！此路不通，回溯)
   
回到x1=2：
       x2=4  (x2=1,2,3全被剪掉)
         │
       x3=1  (x3=2,3,4被剪掉)
         │
       x4=3  → 找到一个解: [2,4,1,3]

3. 子集和数问题 ⭐⭐⭐⭐

问题：给定集合 W 和目标 M，求所有和为 M 的子集。

两个关键剪枝条件：

条件	公式	含义
不超目标	$s + w_k \le M$	选了当前元素不能超目标
还能达到	$s + r_k \ge M$	不选的话，剩下的还够达到目标

其中 $s$ = 当前部分和，$r_k$ = 剩余元素之和。

例：W={5, 10, 12, 13, 15, 18}, M=30

解空间树（部分）：
                root (s=0, r=73)
           ╱ 选5            ╲ 不选5
     s=5, r=68              s=0, r=68
      ╱      ╲               ╱      ╲
   选10    不选10          选10    不选10
 s=15,r=53  s=5,r=53    s=10,r=53  s=0,r=53

检查：s=15, r=53, 选13 → s=28 ≤ 30 ✅, s+53=81 ≥ 30 ✅
     选15 → s=30 = 30 ✅ → 找到解 {5,10,15}！

4. 回溯法 vs 分枝限界法 ⭐⭐⭐⭐

维度	回溯法	分枝限界法
搜索策略	DFS（深度优先）	BFS / 最佳优先（LC）
目标	找出所有解或任意解	找出最优解
活结点结构	隐式栈（递归）	队列(FIFO)或优先权队列(LC)
扩展方式	每次深入一层	每次扩展一个活结点
剪枝依据	约束函数 + 限界函数	上下界函数
空间开销	较小（O(深度)）	较大（O(宽度)）
典型应用	n皇后、图着色、哈密顿环	0/1背包最优解、TSP

---

📜 第9章 分枝限界法 ⭐⭐⭐⭐

1. 分枝限界法核心思想 ⭐⭐⭐⭐⭐

分枝限界法（Branch and Bound）是求解最优化问题的通用框架。它在状态空间树上进行 BFS/最佳优先搜索，利用上下界函数剪枝。

分枝限界法 = 智能搜索 + 上下界剪枝

"分枝"：扩展活结点产生孩子结点
"限界"：用上下界函数剪去不可能产生最优解的分支

三种变体：

类型	活结点表	扩展策略	终止条件	效率
FIFO	队列	先进先出	答案结点出队	低
LIFO	栈	后进先出	答案结点出栈	中（类似回溯）
LC（最小代价）	优先权队列	ĉ 最小的先扩展	ĉ(E) ≥ U	最高 ✅

LC 是实际使用最多的变体，考试也主要考 LC。

2. 代价估计函数 ⭐⭐⭐⭐⭐

ĉ(X)：从根经结点 X 到答案结点的估计最小代价。

$$\hat{c}(X) = f(X) + \hat{g}(X)$$

组成部分	含义	例子
$f(X)$	从根到 X 的已知代价	已选物品总重量、已走路径长度
$\hat{g}(X)$	从 X 到答案结点的估计代价（下界估计）	剩余容量按贪心可装入的价值

关键性质：必须满足 $\hat{c}(X) \le c(X)$（$c(X)$ 是真实最小代价），即 **”估计值 ≤ 真实值”**，否则可能把最优解也剪掉了！

3. 上下界函数详解 ⭐⭐⭐⭐⭐

            ┌─── 上界 u(X)：乐观估计"从X往下最好能多好"
实际值 c(X)─┤
            └─── 下界 ĉ(X)：悲观估计"从X往下至少要多差"

符号	含义	怎么用
$c(X)$	真实最优代价	难以直接计算，是目标
$\hat{c}(X)$	$c(X)$ 的下界估计	① 决定扩展顺序（小的先扩展）② 剪枝（ĉ≥U则剪）
$u(X)$	$c(X)$ 的上界估计	更新全局变量 $U$
$U$	当前最优解的值	剪枝基准：$U = \min{已知可行解的代价}$

剪枝判定：若 $\hat{c}(X) \ge U$，说明即使走 X 这条路最优情况也不会比当前已知解更好，直接剪掉。

LCBB 算法流程图：

          ┌──────────┐
          │ 初始化结点 t │
          └────┬─────┘
               ↓
     ┌─────────────────┐
←────│ 活结点表非空？    │────否──→ 返回答案
│    └────────┬────────┘
│             ↓ 是
│    ┌─────────────────┐
│    │ 取 ĉ 最小的活结点E │
│    └────────┬────────┘
│             ↓
│    ┌─────────────────┐
│    │ ĉ(E) ≥ U ?      │──是──→ 返回答案（LC特有终止）
│    └────────┬────────┘
│             ↓ 否
│    ┌─────────────────┐
│    │ for E的每个孩子X  │
│    └────────┬────────┘
│             ↓
│    ┌─────────────────┐
│    │ ĉ(X) < U ?      │──否──→ 剪枝，不放入
│    └────────┬────────┘
│             ↓ 是
│    ┌─────────────────┐
│    │ X 放入活结点表    │
│    │ 更新 U（若需要）  │
│    └────────┬────────┘
│             │
└─────────────┘

4. 0/1背包问题的分枝限界 ⭐⭐⭐⭐⭐

上界函数（UBB）：对剩余物品按贪心法（可分割）计算最大可能收益。

UBB(X) = 已选物品收益 + 剩余容量按贪心可装入的收益（可能装部分物品）

下界函数（LBB）：已选物品的实际收益（不考虑剩余容量）。也可用贪心构造一个可行解的值。

剪枝：若 $UBB(X) \le$ 当前已知最优收益，则剪掉 X。

手工模拟关键步骤：

假设 M=10，(w,p)=[(4,40),(7,42),(5,25),(3,12)]
排序后按 p/w 降序：(4,40)[10.0], (7,42)[6.0], (5,25)[5.0], (3,12)[4.0]

root(UBB=40+35.7=75.7, 选物品1)
   ├─左孩子(选1, UBB=40+35.7=75.7)
   │   ├─左(选2, UBB=82, 但超重→剪枝)
   │   └─右(不选2, UBB=40+25=65)
   │       ├─左(选3, UBB=65)...
   └─右孩子(不选1, UBB=42+23.8=65.8)...

5. TSP（旅行商问题）⭐⭐⭐

归约矩阵（Reduction）：每行减去该行最小值，每列减去该列最小值。

原始矩阵：         行归约后：         列归约后：
  ∞ 10 17 20       ∞ 0  7  10       ∞ 0  7  9
  15 ∞ 19 28   →   0  ∞ 4  13   →   0  ∞ 4  11
  12 15 ∞ 25       0  3  ∞ 13       0  3  ∞ 11
  20 18 30 ∞       2  0  12 ∞       2  0  12 ∞

行约数=10+15+12+18=55
列约数=...后面的非∞列仍可能需约减

根结点下界 ĉ(root) = 所有约数之和 = 55 + 列约数

选择边后，需要删除对应行和列，并设置禁止回路边（如 $(j,i)$ 在 $(i,j)$ 被选后设为 ∞），再对矩阵重新归约。

---

🎯 期末考法综合总结 ⭐⭐⭐⭐⭐

五大算法策略全景对比

问题类型                  推荐策略           典型问题
─────────────────────────────────────────────────────
求所有可行解             回溯法              n皇后、子集和
求最优解（子问题独立）    分治法              归并排序、快排
求最优解（子问题重叠）    动态规划            LCS、矩阵链、0/1背包
求最优解（贪心可行）      贪心法              一般背包、MST、Dijkstra
求最优解（解空间大且需最优）分枝限界(LC)      0/1背包最优解、TSP

策略	核心哲学	时间复杂度	空间复杂度	是否保证最优
分治法	分而治之，独立求解	视具体算法	递归栈	是
贪心法	局部最优 = 全局最优?	通常 $O(n\log n)$	$O(1)$ 或 $O(n)$	需证明
动态规划	记忆化 + 自底向上	$O(n^2)\sim O(n^3)$	$O(n)\sim O(n^2)$	是
回溯法	DFS + 剪枝	指数（剪枝优化）	$O(深度)$	是（找所有解）
分枝限界	BFS/LC + 上下界剪枝	指数（剪枝优化）	$O(宽度)$	是（找最优解）

必考知识清单

⭐⭐⭐⭐⭐ 绝对重点（必考）

• 大O/Ω/Θ 定义与证明方法
• 主方法求递推式（三种情况判断）
• 贪心法：背包问题（一般 vs 0/1）、Prim / Kruskal、Dijkstra
• DP：LCS、0/1背包递推方程 + 填表 + 回溯
• 回溯法：n皇后（Place函数）、解空间树类型

⭐⭐⭐⭐ 高频考点

• 算法5个特征（有限性 vs 确定性）
• 时间复杂度大小排序
• 快排/归并排序（代码 + 递推分析）
• 贪心正确性证明方法（交换论证）
• 回溯 vs 分枝限界的区别
• LC分枝限界的 ĉ/U 上下界

⭐⭐⭐ 一般考点

• 伸展树三种旋转（zig/zig-zig/zig-zag）
• 跳表结构与概率分析
• DFS四类边 / BFS最短路径
• 双连通分量 / 关节点判定
• Strassen矩阵乘法 / 最佳合并模式
• TSP归约矩阵下界计算

考试答题模板

大O证明题：

① 根据定义写出要证的不等式
② 构造 c 和 n₀（技巧：低阶项放大）
③ 验证当 n ≥ n₀ 时不等式成立
④ 结论：f(n) = O(g(n))

主方法题：

① 写出 a, b, f(n)
② 计算 E = log_b(a)
③ 比较 f(n) 与 n^E
④ 判断情况（找 ε，情况3需验证正则条件）
⑤ 给出答案

算法模拟题：

① 写出初始状态
② 逐步写出每轮的变化（Dijkstra的d/path、DP的填表、Kruskal的选边）
③ 标注关键数据变化（不要跳步！）
④ 给出最终结果 + 验证

DP 设计题：

① 定义状态含义（如 dp[i][j] 表示什么）
② 写出递推方程（基值条件 + 递推式）
③ 确定填表顺序（行→列 / 对角线 / 后→前）
④ 分析时间复杂度
⑤ 如果需要，给出回溯构造解的方法

最后叮嘱

考试提示：

1. 大O证明：找 c 和 n₀，过程写完整，踩分点都在推导步骤
2. 主方法：先算 $\log_b a$，再和 $f(n)$ 比；情况3必须验证正则条件
3. 算法模拟题：一步步写出过程，禁止跳步，中间状态要清晰
4. DP题：递推方程 + 填表 + 回溯构造，三件套缺一不可
5. 代码填空：重点掌握 Partition、Place、Dijkstra初始化、Merge 四个核心函数
6. 判断题：贪心不一定最优（需证明），DP一定最优，0/1背包贪心不对

---