00 算法策略总论与通用解题法

先读这一篇。本课程的大题翻来覆去就是考那几种"算法策略"。这一篇先把所有策略的全景讲清楚，再教你怎么一眼看出一道题该用哪种策略，最后给出每一类大题的"万能答题模板"。把这一篇吃透，后面每个专题文档你都会读得很快。
本篇不堆砌细节（细节在各专题文档），目标是建立"地图"和"通用套路"。

0.1 最基础的三个词：算法、复杂度、规模

在讲策略之前，先把三个贯穿全程的词说清楚。这三个词在判断题、简答题里直接考。

算法（algorithm）：解决某一类问题的、一步一步的、明确的操作序列。它必须满足几条性质（这是填空题原题，见 01）：有输入、有输出、每一步是确定的（不含糊）、在有限步内结束、并且正确（对每个合法输入都给出满足要求的结果）。

问题规模（size，记作 $n$ ）：衡量"这道题的输入有多大"的数字。例如对一个有 $n$ 个数的数组排序，规模就是 $n$ ；对一个有 $n$ 个顶点的图，规模就是顶点数。

时间复杂度（time complexity）：算法要执行多少次"基本操作"（比较、加法这类一步操作），写成关于规模 $n$ 的函数。我们不关心精确的次数，只关心"当 $n$ 很大时，增长得有多快"。

举一个具体例子。下面这段伪代码在 $n$ 个数里找最大值：

text

FindMax(A, n):
    max ← A[1]
    for i ← 2 to n:        // 循环 n-1 次
        if A[i] > max:
            max ← A[i]
    return max

它做了 $n - 1$ 次比较。当 $n$ 很大时， $n - 1$ 和 $n$ 几乎一样，所以我们说它的时间复杂度是 $O (n)$ （读作"大 O n"，意思是"和 $n$ 同一个增长档次"）。 $O (\cdot)$ 这个记号的精确含义在 01 详细讲，这里你只需要知道：复杂度就是用来描述"算法快慢随规模怎么变"的。

为什么要关心复杂度？因为同一个问题，不同算法的复杂度可能是 $O (n)$ 、 $O (n \log n)$ 、 $O (n^{2})$ 、 $O (2^{n})$ 。当 $n = 1000$ 时， $O (n)$ 是一千次操作， $O (n^{2})$ 是一百万次， $O (2^{n})$ 是一个 301 位的天文数字。算法设计的核心目标，就是用更低的复杂度解决同一个问题。 这就是为什么每道大题最后都要"分析时间复杂度并与蛮力法相比较"。

蛮力法（brute force，又称穷举法）：不动脑子，把所有可能情况都试一遍。它一定能得到正确答案，但通常复杂度很高。各种"策略"存在的意义，就是比蛮力法更快。所以大题里"与蛮力法比较"几乎是固定要求。

0.2 九大算法策略全景

本课程涉及的算法可以归到下面几大类。这张表是整门课的地图，先扫一遍建立印象，每一类后面都有专门文档深入。

策略	一句话本质	何时用它	典型考题	专题文档
分治	把大问题切成几个同类的、互不相干的小问题，分别解决再合并	子问题彼此独立、不重叠	逆序对、股票买卖、网球赛	`02`
减治	把规模缩小一截（通常减半或减一），只解其中一个子问题	缩小规模后只需处理一部分	二分查找、求 $⌊ \log_{2} N ⌋$	`03`
变治	先变形/预处理输入（如排序、换数据结构），再在新形式上求解	变形后问题变简单	多数元素、BST/AVL	`03`
动态规划	把大问题拆成子问题，但子问题互相重叠，用表把每个子问题的解存下来，避免重复计算	子问题重叠、有最优子结构	矩阵链乘、LCS、资源分配	`04`
贪心	每一步都做当前看起来最好的选择，不回头	局部最优能导出全局最优	多机调度、Huffman	`05`
回溯	在"所有可能解"组成的树上深度优先地搜，走不通就退回	要找出满足约束的解	SAT 求解	`06`
分支限界	和回溯类似，但用"界函数"估算前景、按优先级搜、专门求最优解	在可行解中求最优	中转贸易、布线	`06`
概率算法	在计算中随机地做选择，用随机性降低复杂度或简化问题	确定性算法太慢或太难	指纹法、随机取大值	`07`
近似算法	对很难的问题，不求最优解，求一个"差不了太多"的解，并保证差距	问题是 NP 难、求不出最优	TSP 最近邻、装箱	`08`
智能优化	模仿自然过程（退火、进化）的启发式搜索	超大规模难优化问题	模拟退火、遗传算法	`10`

下面对每一类再补一句"它到底在干嘛"，配一个最小的例子。

分治（divide and conquer）

三步：① 分（divide）——把规模为 $n$ 的问题分成若干个规模更小的同类子问题；② 治（conquer）——递归地解这些子问题；③ 合（combine）——把子问题的解合并成原问题的解。

最经典的例子是归并排序：把 $n$ 个数从中间切成两半（分），分别排好序（治），再把两个有序的半段合并成一个有序的整段（合）。它的复杂度满足递推式 $T (n) = 2 T (n / 2) + O (n)$ ，解出来是 $O (n \log n)$ （怎么解见 01）。

判断分治的关键：切出来的子问题必须互不相干。归并排序里，左半段排序和右半段排序毫不影响，这就是分治。

减治（decrease and conquer）

减治也是把规模变小，但和分治的区别是：分治要解多个子问题，减治通常只解一个。

最经典的例子是二分查找：在一个排好序的数组里找某个数 $x$ ，先看正中间那个数，如果 $x$ 比它小就只在左半边找，比它大就只在右半边找——每次把范围砍掉一半，而且只往一边走。复杂度 $T (n) = T (n / 2) + O (1) = O (\log n)$ 。

减治又细分三种（这是简答题考点，见 03）：减常数（每次减固定一截，如减 1）、减常数因子（每次按比例减，如减半）、减可变规模（每次减的量不固定，如二叉查找树）。

变治（transform and conquer）

变治的核心是"先把问题变个形式，变成更好处理的样子，再求解"。

最经典的例子是多数元素问题：找出数组里出现次数超过一半的数。蛮力法 $O (n^{2})$ 。变治法：先把数组排序（这就是"变形"），排完之后相同的数都挨在一起，扫一遍找最长的连续相等段即可，复杂度降到 $O (n \log n)$ 。这里"排序"就是变治。

动态规划（dynamic programming，简称 DP）

DP 和分治都是"拆成子问题"，但有一个致命区别：DP 的子问题会重复出现。

举例：求斐波那契数 $F (n) = F (n - 1) + F (n - 2)$ 。如果直接递归，算 $F (5)$ 要算 $F (4)$ 和 $F (3)$ ，算 $F (4)$ 又要算 $F (3)$ 和 $F (2)$ …… $F (3)$ 被算了很多次，指数级浪费。DP 的做法是：开一个表，算出来的每个 $F (i)$ 就存进表里，下次要用直接查表，于是每个子问题只算一次，复杂度从指数降到 $O (n)$ 。

DP 是本课程分值最高、最套路化的大题，一定要重点练（见 04）。它的标准作答四件套（状态、决策、转移方程、边界）在本篇 0.4 节和 04 都会讲。

贪心（greedy）

贪心每一步都选当前最优，并且选了就不反悔。

举例：找零钱问题。要用最少的硬币凑出 63 分，硬币有 25、10、5、1 分。贪心做法：每次都拿不超过剩余金额的最大面值——先拿 2 个 25（剩 13），再拿 1 个 10（剩 3），再拿 3 个 1，共 6 枚。对这套面值，贪心恰好能得到最优解。

⚠️ 但贪心不总是对的。如果硬币面值是 1、3、4，要凑 6 分：贪心先拿 4（剩 2），再拿 2 个 1，共 3 枚；而最优是 3+3，只要 2 枚。贪心是否能得到最优解，需要证明（背后的理论是"拟阵"，见 05）。所以贪心大题常常会说"不一定要找到最优解"。

回溯（backtracking）与分支限界（branch and bound）

这两个放一起讲，因为它们都建立在解空间树这个概念上（见本篇 0.5），是本课程的重点难点。

回溯：把所有可能的解组织成一棵树，用深度优先搜索（一条路走到黑，走不通就退回上一步换条路）去遍历，遇到违反约束的分支就剪掉（不再往下搜）。它用来找出满足约束的解。
分支限界：和回溯很像，但它用一个界函数估算"从这个分支往下最好能到多好"，据此优先搜索最有希望的分支，并剪掉不可能更优的分支。它专门用来求最优解。

二者区别是高频选择题（见 06、11）：求解目标相同（都在解空间树上搜），搜索方式不同（回溯用深度优先，分支限界常用广度优先或优先队列）。

概率算法（probabilistic / randomized algorithm）

在算法里加入随机选择。分四种（见 07）：

数值概率算法：用随机采样求数值近似解（如用随机投点估算 $π$ ）。
蒙特卡罗（Monte Carlo）算法：总能给出解，但解可能是错的，且无法判断对错。
拉斯维加斯（Las Vegas）算法：不一定给出解，但只要给出就一定对。
舍伍德（Sherwood）算法：用随机化消除最坏情况对特定输入的依赖（如随机化快速排序）。

这四种的区别，尤其是蒙特卡罗 vs 拉斯维加斯，是年年必考的判断/简答（见 07、11）。

近似算法（approximation algorithm）

有些问题（NP 难问题，见 09）目前没人能在合理时间内求出最优解。近似算法退而求其次，求一个"接近最优"的解，并给出性能比（近似解和最优解最多差多少倍，见 08）。

智能优化算法（metaheuristics）

邻域搜索、模拟退火、遗传算法等，是面向超大规模难优化问题的"启发式"方法——不保证最优，但实践中往往能找到不错的解（见 10）。

0.3 怎么判断一道大题该用哪种策略

考试大题通常会直接告诉你用哪种策略（"设计一求解……的分治算法""基于动态规划思想……"），这种照着对应文档的模板做即可。但有时要你自己判断，或要你"分别用蛮力、分治、动态规划求解"。下面是判断清单。

第 1 步：看题目有没有明说。 出现下列字眼直接对号入座：

题目里的字眼	用哪种策略
"分治""divide"	分治（`02`）
"减治""变治""减治思想"	减治/变治（`03`）
"动态规划""DP""状态转移方程"	动态规划（`04`）
"贪心""贪婪""greedy"	贪心（`05`）
"回溯""画出搜索树""SAT"	回溯（`06`）
"分支限界""分支定界""界函数""二叉搜索树+最优"	分支限界（`06`）
"概率算法""随机""指纹""输出正确的概率"	概率算法（`07`）
"近似算法""性能比"	近似算法（`08`）
"遗传算法""模拟退火""邻域搜索"	智能优化（`10`）

第 2 步：如果没明说，看问题的"形状"。

问题能切成互不相干的小块，分别解完一拼就行 → 分治。例：逆序对、最大子段。
每一步能砍掉一大半规模、只往一边走 → 减治。例：在有序数组里查找。
子问题会反复用到同一个小问题，或题目要"求最大/最小/最优值"且能写出"当前最优 = 某个子问题最优 + 这一步的代价" → 动态规划。例：所有"资源分配""最长××""最优结合"。
题目让你"每步选最好的"、或明说"不一定要最优" → 贪心。
要列举/找出满足若干约束条件的解 → 回溯。
要在满足约束的解里求最优，且数据规模大需要剪枝 → 分支限界。

第 3 步：识别"最优化问题"的两大武器——DP 还是贪心。 这是最容易纠结的。判断口诀：

如果"每一步的局部最优选择"能拼出全局最优（且你能说服自己/给出理由）→ 贪心，简单快。
如果局部最优不一定对，必须考虑各种组合、比较所有子问题的解 → 动态规划，稳妥。
拿不准就用动态规划：DP 几乎总能保证最优，只是慢一点。考场上若题目要"最优解"又没说用贪心，优先 DP。

（DP 与贪心的区别详见 04 和 05。）

0.4 解空间树：回溯与分支限界的统一概念

回溯和分支限界都绕不开解空间树，这是本课程最重要的概念之一，单独讲清楚。

解空间（solution space）：一个问题所有"可能的解"的集合。解空间树（state-space tree，又称状态空间树）：把这些可能解按"一步步做决策"的过程组织成一棵树——树根是"什么都还没决定"，每往下一层就多决定一个变量，叶子就是一个完整的候选解。

举一个最具体的例子：子集问题。有 3 个物品 ${1, 2, 3}$ ，要枚举所有子集（每个物品"选"或"不选"）。解空间树这样长：

                      根(还没决定)
                 选1 /        \ 不选1
              {1}              {}
          选2 /   \不选2     选2 /  \不选2
        {1,2}    {1}       {2}     {}
       选3/\   选3/\     选3/\    选3/\
   {1,2,3}{1,2}{1,3}{1} {2,3}{2} {3} {}

每个物品对应一层，每层分两枝（选/不选），走到叶子就得到一个具体子集。这种"每个元素选或不选"的树叫子集树（subset tree），有 $n$ 个元素时叶子有 $2^{n}$ 个（选择题原题，见 11、06）。

另一种常见的是排列树（permutation tree）：要枚举 $n$ 个元素的所有排列顺序时用，叶子有 $n!$ 个。例如旅行商问题枚举走访城市的顺序。

回溯就是在解空间树上做深度优先搜索：从根出发，沿一条枝一直往下走（一直做决策），如果走到某个结点发现"这条路已经违反约束、不可能有解了"，就剪枝（不再往下，退回上一个分叉点换另一枝）。这个"退回"的动作就是"回溯"。

分支限界也是在解空间树上搜，但它额外算一个界（bound）：估计"从当前结点往下，最好/最差能得到多优的解"。用这个界，它能① 优先扩展最有希望的结点（按优先级而非死板地深度优先）；② 把"界已经比当前找到的最优解还差"的整个分支剪掉。

这套语言（解空间树、子集树、排列树、剪枝、界）在选择题、回溯题、分支限界题里反复出现，务必记牢（详见 06）。

0.5 递推式：分析一切递归算法复杂度的通用工具

只要算法里有"自己调用自己"（递归），它的复杂度就写成一个递推式（recurrence）——用"小规模的复杂度"表示"大规模的复杂度"。这是分治、减治大题的固定收尾环节，也单独出递推式求解题（T1～T5）。

递推式长什么样：以归并排序为例，

T (n) = 2 T (n / 2) + O (n) .

它的含义逐项解释： $T (n)$ 是"规模为 $n$ 时的总操作次数"；等号右边 $2 T (n / 2)$ 表示"要解 2 个规模为 $n / 2$ 的子问题"； $O (n)$ 表示"合并这两个子问题的解需要额外 $O (n)$ 的工作"。再配一个边界条件（如 $T (1) = O (1)$ ，规模为 1 时直接出结果）。

解递推式有两个常用工具（详细讲解和例题在 01）：

主定理（Master Theorem）：专门对付形如 $T (n) = a T (n / b) + f (n)$ 的递推式（ $a$ 个子问题、每个规模缩小到 $1 / b$ 、合并代价 $f (n)$ ）。它直接给出答案，是考场最快的方法。
迭代展开法：把递推式一层层代入展开，找出规律再求和。当主定理不适用时用它。

为什么必须会解递推式：每道分治/减治大题最后都要"分析时间复杂性"，标准做法就是写出递推式再解出来。例如：

T (n) = 2 T (n / 2) + O (n) = O (n \log n), T (n) = T (n / 2) + O (1) = O (\log n) .

这两个结论会被反复用到，建议直接记住。

0.6 动态规划通用四步模板（最高频大题，必背）

DP 大题（投资分配、生产库存、货车分配、矩阵链乘等）的作答有完全固定的格式。阅卷就看你这四样写没写、写没写对。把这个模板背下来，任何 DP 题都照着填。

第 1 步：设状态变量。 状态就是"描述当前局面要哪几个数"。资源分配类题目，状态通常是"阶段编号 + 当前还剩多少资源"。

写法示例："设阶段 $k$ 表示第 $k$ 个项目；状态 $x_{k}$ 表示可分配给第 $k$ 到第 $n$ 个项目的资金。"

第 2 步：设决策变量。 决策就是"这一步你要做的选择"。

写法示例："决策 $u_{k}$ 表示分配给第 $k$ 个项目的资金， $0 \leq u_{k} \leq x_{k}$ 。"

第 3 步：写状态转移方程。 这是核心，表示"当前最优 = 在所有可能决策里挑一个，使得【这一步的收益】加上【剩下局面的最优】最大"。资源分配类的通用形式：

f_{k} (x_{k}) = max_{0 \leq u_{k} \leq x_{k}} {g_{k} (u_{k}) + f_{k + 1} (x_{k} - u_{k})}

逐项解释： $f_{k} (x_{k})$ 是"从第 $k$ 个项目开始、手上有 $x_{k}$ 资源时能拿到的最大总收益"； $g_{k} (u_{k})$ 是"给第 $k$ 个项目投 $u_{k}$ 的直接收益"（查题目给的表）； $f_{k + 1} (x_{k} - u_{k})$ 是"把剩下的 $x_{k} - u_{k}$ 资源留给后面项目的最优收益"；外层 $max$ 表示"在所有可能的投资额 $u_{k}$ 里挑使总和最大的那个"。

第 4 步：写边界条件。 递推总得有个起点。

写法示例："边界 $f_{n + 1} (x) \equiv 0$ （没有项目可投时收益为 0）。"

第 5 步：手工填表求解。 从边界出发，一个阶段一个阶段、一个状态一个状态地算，把每一步的 $max$ 是怎么取到的写清楚，最后倒推出每个项目实际投了多少。这一步必须把计算过程写出来，只写答案不给分。

一个完整的资源分配 DP 手算示范见 04，这里先把模板记住。所有这类题（P3 投资、P4 生产库存、P5 货车、P6 货物）都是这一个模板的换皮。

0.7 各类大题的"万能答题模板"

下面给出每种大题的"骨架"。考场上先把骨架默写下来，再往里填具体内容，保证不漏采分点。每个模板的完整范例在对应专题文档。

模板 A：分治大题（见 `02`）

【思路】把规模为 n 的问题从中间分成两半（或若干份）：
  ① 递归解左半 / 子问题1；
  ② 递归解右半 / 子问题2；
  ③ 合并：处理"跨越两半"的情况，把子问题的解拼成原问题的解。
【伪代码】（写出递归函数，含递归出口 if n 很小: 直接解）
【复杂度】写出递推式 T(n)=2T(n/2)+O(合并代价)，解得 O(...)。
【与蛮力比较】蛮力 O(n^2)（或更高），分治 O(n log n)，n 大时分治更优。

模板 B：动态规划大题（见 `04`）

【状态变量】设 ...
【决策变量】设 ...
【状态转移方程】f_k(...) = max/min { ... }
【边界条件】f(...) = ...
【手工求解】列表，从边界逐阶段计算，写出每步的 max/min 取值过程。
【结果】最优值 = ...，最优方案 = ...（倒推得出）。
【复杂度】O(...)。

模板 C：贪心大题（见 `05`）

【贪心策略】每一步选择 ...（说清按什么标准选、选什么）。
【伪代码】（通常是：排序 + 循环依次贪心选取）
【复杂度】排序 O(n log n) + ... = O(...)。
【说明】贪心不一定最优（若适用，给出近似比，如列表调度 2-1/m）；
        若要保证最优需用动态规划。

模板 D：回溯大题（SAT，见 `06`）

【分支策略】按变量顺序 p,q,r,s 依次取值，左枝=1(真)、右枝=0(假)。
【过程】每代入一个变量就化简 CNF（合取范式）：
        - 某子句中有文字为真 → 整个子句被满足，划掉；
        - 某子句所有文字为假 → 子句变空 → 矛盾 → 剪枝回溯。
【画搜索树】每个结点标注化简后的 CNF，标明在哪剪枝。
【结论】给出一组可满足赋值，或说明无解。

模板 E：分支限界大题（四问，见 `06`）

① 如何构造搜索树（要求二叉）：每个对象一层，左枝=选/经过，右枝=不选/不经过。
② 遍历原则：不满足剪枝条件且有子树就前进；多选择处分支(先左后右)；
   左子树搜完或被剪则回溯到父结点。
③ 界是什么、为何正确有效：
   下界 = 已付出代价 + 由当前点到终点的"最小剩余代价"(放宽约束求得，故是合法下界)；
   上界 = 迄今找到的最优解；当 下界 ≥ 上界 时剪枝。
④ 伪代码：递归 search(已选集, 已弃集)，到终点更新最优，否则分左右子树递归。

模板 F：NP 完全性证明（两步，见 `09`）

要证问题 X 是 NP 完全的，证两件事：
① X ∈ NP：给一个"证书"(候选解)，说明能在多项式时间内验证它对不对。
② 已知的某 NP 完全问题 Y ≤_p X：把 Y 的任意实例在多项式时间内
   构造成 X 的一个实例，使得"Y 是 yes 实例 ⟺ X 是 yes 实例"。
结合①②，X 是 NP 完全的。∎

模板 G：性能比 / 下界类简答（见 `08`）

性能比定义：η = max{ c/c*, c*/c }，恒 ≥ 1（极小化取 c/c*，极大化取 c*/c）。
⚠️ 单个实例的比值只是性能比的"下界"，不能断定就是性能比——
   性能比是对"所有实例"的最坏比值。
下界证明方法（任举几种）：平凡下界、判定树/信息论下界、对手论证、问题归约。

0.8 五大策略适用条件对照（简答 Q19 原题，必背）

原题（来源 试卷5）：请分别说明分治策略、动态规划、贪心选择策略、回溯法和分支限界法在实际应用中的适用条件。

这是一道纯送分简答，把下面五条背下来即可：

分治：问题能分解为规模更小的同类、相互独立的子问题，且子问题的解能合并成原问题的解（常与递归对应）。
动态规划：问题能分解为子问题，但子问题相互重叠（不独立），且具有最优子结构（大问题的最优解包含子问题的最优解）；常用于求具有某种最优性质的问题，自底向上、用表记忆已算结果。
贪心：具有贪心选择性质与最优子结构——每一步的局部最优选择能导向全局最优解。
回溯：需要求出满足约束条件的所有解（或一个可行解），在解空间树上深度优先搜索并剪枝。
分支限界：需要在满足约束条件的解中求最优解，用界函数剪枝，按广度优先或优先队列方式扩展活结点。

0.9 通用易混概念对照总表

下面这些"成对"的概念是判断题、选择题、简答题最爱挖坑的地方。这里给出总表速记，每对的详细辨析在对应专题文档。

概念 A	概念 B	关键区别	详见
分治	动态规划	分治子问题独立；DP 子问题重叠，要存表	`02`/`04`
贪心	动态规划	贪心每步选当前最优不回头、不一定最优；DP 考虑所有组合、保证最优	`05`/`04`
回溯	分支限界	目标相同（解空间树上搜）；回溯深度优先找可行解，分支限界广度优先/优先队列求最优	`06`
蒙特卡罗	拉斯维加斯	蒙特卡罗总有解但可能错；拉斯维加斯解必对但可能不给解	`07`
归约 (reduce)	转化 (transform)	归约：拿 B 的算法当子程序去解 A；转化：把 A 的实例构造成 B 的实例且 yes/no 对应	`09`
P 类	NP 类	P：能在多项式时间求解；NP：能在多项式时间验证一个给定解	`09`
NP 完全 (NPC)	NP 难 (NP-hard)	NPC 必须本身属于 NP；NP-hard 不要求属于 NP，范围更广	`09`
减治	分治	减治通常只解一个子问题；分治解多个	`03`
伪多项式	真多项式	伪多项式是关于输入数值大小的多项式，不是关于输入位数的	`07`/`08`

⚠️ 历年最毒的两个判断陷阱（务必记住，见 11、08、09）：

"NP 完全问题比其它所有 NP 问题都难"——错。 NP 完全问题之间是等难的（互相能多项式转化），只是"至少和其它 NP 问题一样难"，不是严格更难。
"某实例近似解是最优解的 3 倍，所以性能比是 3"——错。 单个实例只给出性能比的一个下界；性能比是对所有实例取的最坏比值，不能由一个实例断定。

0.10 考场通用策略

先做判断题和简答概念题：这些是确定分，且做得快。把 11 背熟，这部分应当几乎全拿。
DP 大题优先攻：分值最高、最套路化。严格按 0.6 的四步模板写，把手算表格列全。
每道大题的"分析复杂度"和"与蛮力比较"不要漏：这是固定采分点，哪怕算法没写完，把递推式和复杂度结论写上也有分。
回溯/分支限界题先把"框架四问/模板"默写上：即使具体的树画不全，构造方法、遍历原则、界、伪代码这几块的通用描述也是采分点（见 06）。
判断题拿不准时的倾向：涉及"最/所有/一定/不可能"这类绝对化措辞的，往往是错的陷阱（如"NP 完全是所有问题中最难的""平均复杂度能降得更低"）；涉及定义复述的，往往是对的。这只是辅助手段，能背就别猜。
公式记号一律用规范写法：复杂度写 $O (n \log n)$ 不要写成 "nlogn"，集合关系写 $P \subseteq N P$ ，这些在阅卷时是规范分。

0.11 本篇与各专题文档的关系

本篇是"地图 + 通用套路"。每一类策略的完整理论、每一道历年原题的逐题精解、可照抄的完整解答，都在对应的专题文档里：

数学工具（复杂度、递推式）→ 01
五大策略大题 → 02（分治）、03（减治变治）、04（动态规划）、05（贪心）、06（回溯/分支限界）
概率、近似、下界 → 07、08
理论（P/NP、NP 证明）→ 09
智能优化 → 10
判断/选择/填空速记 → 11

读完本篇，建议直接去 11 把判断题过一遍（最快见效），再按 01 → 04 → 05 攻克核心大题。

00 算法策略总论与通用解题法 ​

0.1 最基础的三个词：算法、复杂度、规模 ​

0.2 九大算法策略全景 ​

分治（divide and conquer） ​

减治（decrease and conquer） ​

变治（transform and conquer） ​

动态规划（dynamic programming，简称 DP） ​

贪心（greedy） ​

回溯（backtracking）与分支限界（branch and bound） ​

概率算法（probabilistic / randomized algorithm） ​

近似算法（approximation algorithm） ​

智能优化算法（metaheuristics） ​

0.3 怎么判断一道大题该用哪种策略 ​

0.4 解空间树：回溯与分支限界的统一概念 ​

0.5 递推式：分析一切递归算法复杂度的通用工具 ​

0.6 动态规划通用四步模板（最高频大题，必背） ​

0.7 各类大题的"万能答题模板" ​

模板 A：分治大题（见 02） ​

模板 B：动态规划大题（见 04） ​

模板 C：贪心大题（见 05） ​

模板 D：回溯大题（SAT，见 06） ​

模板 E：分支限界大题（四问，见 06） ​

模板 F：NP 完全性证明（两步，见 09） ​

模板 G：性能比 / 下界类简答（见 08） ​

0.8 五大策略适用条件对照（简答 Q19 原题，必背） ​

0.9 通用易混概念对照总表 ​

0.10 考场通用策略 ​

0.11 本篇与各专题文档的关系 ​