算法刷题系列路线图：从基础结构到动态规划与图论

算法刷题系列路线图：从基础结构到动态规划与图论

算法题目看起来很多，解法却常常建立在少数几种结构和思维方式上。这个系列把一组常见刷题主题重新编排成一条由浅入深的路线：先学会读题和模拟，再掌握线性数据结构与序列技巧，随后进入搜索、树、图、区间结构和动态规划。

本路线不是按题目难度从易到难的排行榜。学习时应先理解“为什么这种状态或结构能解决问题”，再做题验证；如果某一模块的前置概念还不稳，可以先回到前面的模块练习。

系列目标

完成系列后，希望读者能够：

• 将自然语言题意转成输入、状态、操作和输出。
• 根据数据规模估算时间与空间复杂度，排除明显不可行的做法。
• 识别数组、字符串、树、图等问题背后的常见结构。
• 解释所选算法为什么正确，而不只是记住一段模板代码。
• 用 Java 和 Python 分别实现核心思路，并通过边界用例验证。

系列篇次与依赖关系

全系列共 56 篇，按“状态建模 → 常用结构 → 搜索与递归 → 图模型 → 区间结构 → 动态规划”的顺序组织。每篇的“承接”说明建议先掌握的前置概念；可以跳读，但遇到术语不熟时应回到对应篇次。

第一阶段：先把题意变成可执行的算法

这一阶段建立解题的共同语言：状态是什么、如何记录信息、如何缩小候选。

1. 模拟法：从题意到状态更新（已完成草稿）——定义状态，逐条执行规则，先建立正确基线。
2. 哈希表：用空间换查找（已完成草稿）——将历史扫描变成键值查询；承接模拟中的重复查找。
3. 排序：把无序问题变成有序结构——学习比较规则、稳定性和排序后可利用的性质；承接数组与查找。
4. 数学：用数与不变量缩小问题（已完成草稿）——整理取模、最大公约数、计数和简单数论；承接复杂度与边界分析。
5. 位运算：用二进制表达状态——理解掩码、异或、置位和清位；为子集枚举和状压 DP 做准备。
6. 二进制枚举：遍历小规模集合的所有子集——将位掩码映射为选择状态；承接位运算。
7. 打表：预计算换取查询效率——识别有限状态空间与重复查询；对比记忆化搜索，明确空间与初始化代价。
8. 表达式计算：从符号串到运算结果——处理括号、优先级和操作数；连接栈、递归解析与状态维护。

阶段检查：能为一个新题写出状态定义、操作顺序、终止条件和边界样例。

第二阶段：掌握线性结构与序列技巧

这一阶段从数据组织方式出发，逐步学习扫描、区间统计和字符串处理。

1. 栈：处理后进先出的状态——掌握入栈/出栈不变量；为括号、单调栈和表达式计算打基础。
2. 队列：按到达顺序处理任务——理解先进先出；为 BFS 和滑动窗口队列打基础。
3. 链表：处理节点引用与局部重连——掌握虚拟头节点、删除和反转；对比数组的随机访问。
4. 双指针：让两个位置协同移动——根据有序性或区间约束减少重复扫描；承接排序。
5. N 数之和：组合哈希与双指针——从两数之和推广到多元素组合，并正确去重；承接哈希表、排序和双指针。
6. 移除元素：用读写指针原地筛选——维护有效前缀，理解覆盖顺序和返回长度；承接双指针。
7. 前缀和：把区间和变成前缀差——支持静态区间查询；承接数组遍历和哈希计数。
8. 差分：把区间修改变成边界变化——用差分数组处理批量区间更新；承接前缀和的逆向关系。
9. 滑动窗口：维护满足条件的连续区间——学习窗口不变量和左右边界的单调移动；承接双指针、前缀和。
10. 回文串问题：利用对称性减少比较——从中心扩展到字符串区间判断；承接双指针和字符串索引。
11. 括号问题：用栈和前缀约束检查合法性——区分匹配、最长有效段和多类型括号；承接栈。
12. 子串匹配：在文本中高效寻找模式——理解朴素匹配与利用已知前缀信息的优化；承接字符串与前缀思想。
13. 字典树：按公共前缀组织字符串——支持前缀查询、插入和搜索；承接哈希表，同时比较空间取舍。

阶段检查：能够解释每种结构维持的不变量，并说明它解决了哪类重复工作。

第三阶段：搜索、候选维护与贪心

这一阶段学习如何利用单调性缩小范围、维护动态候选，以及证明局部策略可行。

1. 二分查找：在单调条件中定位边界——明确闭区间/半开区间、循环不变量和边界返回；承接排序。
2. 三分搜索：在单峰函数中定位极值——说明单峰前提与精度/整数域处理；承接二分的区间收缩思想。
3. 堆：动态维护最值与 Top-K——理解优先队列操作和复杂度；承接排序、队列。
4. 多路归并：用小顶堆合并多个有序流——每次只维护各路当前候选；承接堆和排序。
5. 贪心算法：从局部选择到正确性证明——用交换论证、反证或不变量验证策略；承接排序、堆和区间思维。

阶段检查：二分能说清单调条件，贪心能给出证明而非只凭样例。

第四阶段：树、递归与组合搜索

树结构、遍历和回溯共享递归思维；本阶段从树的定义推进到一般搜索。

1. 二叉树：从节点关系建立递归模型——理解左右子树、空节点和递归返回值。
2. 树的搜索：前序、中序、后序与层序——依据问题选择遍历顺序；承接二叉树与栈/队列。
3. DFS：沿路径深入并维护访问状态——区分树递归与图搜索中的 visited；承接树的递归遍历。
4. BFS：按层扩展状态空间——用队列处理无权最短步数；承接队列和树的层序遍历。
5. 回溯算法：做选择、递归、撤销选择——定义路径、候选集和剪枝条件；承接 DFS。
6. 组合总和：在回溯中处理复用与去重——通过起始下标和排序剪枝控制组合枚举；承接回溯、排序。
7. 数独问题：把约束满足转成搜索——用行、列、宫约束剪枝；承接回溯与位掩码。
8. 分治：拆分子问题并合并结果——明确子问题规模、独立性和合并过程；承接递归。
9. 启发式搜索：用估价信息引导探索——讨论搜索策略、启发函数和最优性前提；承接 BFS/DFS 与状态建模。

阶段检查：能明确搜索状态、选择集合、终止条件、剪枝条件和回退动作。

第五阶段：把关系建模为图

树可以看作特殊图。本阶段从连通性和图遍历开始，再处理依赖、连通网络和最短路径。

1. 并查集：维护动态连通分量——用路径压缩与按秩合并回答连通性；承接树形结构。
2. 图论 BFS：在无权图中求最少边数——把普通 BFS 推广到邻接表和多源起点；承接队列、BFS。
3. 图论 DFS：遍历连通分量和结构——处理访问标记、环检测和连通块；承接 DFS。
4. 拓扑排序：安排有向无环图的依赖顺序——用入度队列或 DFS 序检测有向环；承接图遍历和队列。
5. 最小生成树：用最低代价连接所有顶点——比较 Kruskal 与 Prim，并说明何时使用并查集/堆；承接排序、并查集和堆。
6. 最短路：按边权条件选择算法——区分无权、非负权和含负权场景，避免算法误用；承接图 BFS、堆和松弛思想。

阶段检查：给定一张图，能说明它有向/无向、带权/无权、是否可能有环，并据此选算法。

第六阶段：用专门结构处理区间与事件

当前缀统计和普通扫描不足以应付频繁查询时，引入维护候选或区间信息的数据结构。

1. 单调栈：维护最近的更大/更小候选——理解弹出条件和每个元素至多入栈/出栈一次；承接栈与排序。
2. 单调队列：维护滑动区间中的极值——按索引过期并维护单调性；承接队列、滑动窗口。
3. 树状数组：维护前缀聚合与单点更新——掌握 lowbit、下标转换及区间查询；承接前缀和、差分。
4. 线段树：维护区间查询与更新——定义节点信息、合并规则和懒标记；承接树状数组与分治。
5. 扫描线：按事件顺序维护动态状态——把几何或区间问题转成排序后的事件处理；承接排序、堆、线段树。

阶段检查：能写清数据结构保存的摘要信息、更新规则、查询规则和单次复杂度。

第七阶段：动态规划与状态压缩

最后把“搜索状态”升级为可复用的子问题结果，逐步覆盖一维、序列、区间和高维状态。

1. 记忆化搜索：缓存重复递归状态——从搜索树中识别重叠子问题；承接 DFS、回溯。
2. 线性 DP：从前缀状态递推当前位置——明确状态定义、初始化、转移和遍历顺序；承接记忆化搜索。
3. 序列 DP：描述序列之间的选择关系——处理子序列、最长上升子序列或两个序列的匹配；承接线性 DP。
4. 背包 DP：在容量约束下做选择——区分 0/1、完全和多重背包，并说明循环方向；承接线性 DP。
5. 状态机 DP：用有限状态表达阶段变化——把持有/未持有等状态及合法转移显式化；承接序列 DP、背包思维。
6. 区间 DP：按区间长度逐步合并子问题——枚举分割点或最后操作；承接分治与线性 DP。
7. 数位 DP：按数字位统计受上界约束的方案——处理前导零、上界标记和限制状态；承接状态 DP 与记忆化搜索。
8. 状压 DP：用位掩码表示集合状态——将小规模集合的选择与 DP 结合；承接位运算、二进制枚举、背包 DP。
9. 博弈论：从可达后继判断胜负状态——建立必胜/必败状态和转移；承接状态 DP 与图搜索。
10. 矩阵快速幂：加速线性递推的多步转移——把状态转移写成矩阵并用快速幂处理大步数；承接线性 DP、矩阵乘法。

完成系列后：能够从暴力递归识别重叠子问题，定义状态、写出转移，并以初始化、遍历顺序和复杂度分析验证设计。

当前进度

篇次	主题	状态
1	模拟法：从题意到状态更新	草稿已完成
2	哈希表：用空间换查找	草稿已完成
3–56	其余主题	已完成路线编排，后续逐篇撰写

篇次按学习依赖组织，不要求按日历连续发布。每篇正式发布前都应独立验证示例代码，并按统一文章结构补足推导、复杂度、测试和易错点。

每篇文章的统一结构

为了让系列不变成“代码合集”，每篇教程尽量按同一条推理路径展开：

1. 问题信号：题目出现哪些特征时可以考虑该方法。
2. 朴素做法：先建立正确但可能低效的基线。
3. 关键观察：指出重复工作、可维护的不变量或状态关系。
4. 算法推导：说明如何从观察得到解法，并解释正确性。
5. Java 与 Python 实现：保持两种语言的变量含义和边界处理一致。
6. 复杂度分析：明确时间复杂度、额外空间和适用前提。
7. 边界测试：覆盖空输入、单元素、重复值、最大规模等相关情况。
8. 易错点与相邻题型：帮助读者决定下一步练习什么。

选题与版权说明

本系列的主题清单参考本地资料目录中可见的算法主题名称；文章正文、例题、推导和代码将独立撰写，不转录或改写源 PDF 的正文。源资料及其原文权利归原作者或相应版权方所有；本系列不表示获得原文转载授权。

从哪里开始

建议按模块顺序学习。本文之后先从“模拟”开始，因为它能训练把题意拆成状态和操作；有了这个习惯，再学习哈希、指针、搜索和动态规划时，会更容易解释算法为什么正确。