NORTH STAR / 长期目标
学到什么程度才算真正掌握？
面对新问题能提出状态与不变量，选择算法范式，证明正确并清楚表达时间/空间边界。
设计、证明、分析CS-20 / CORRECTNESS
算法与证明Algorithms
把算法训练从“记题解”改造成问题建模、设计范式、正确性证明、复杂度分析和实验验证的闭环。
PREREQUISITES / 先修检查
进入路线前
- 熟悉常见数据结构
- 掌握求和、对数与数学归纳法
- 能独立实现并调试中等规模程序
- 了解渐近复杂度和递归
FOUNDATIONS / 地基
第一轮优先补齐
- 循环/递归不变量
- 递推式与主定理
- 图、树、堆、并查集
- 反例、归约与下界意识
STAGED ROUTE / 阶段路线
用可验证产出推进，而不是只计算观看时长
阶段可并行回看；勾选只表示完成过该阶段的产出与自检，不代表永久掌握。
A14 周 证明与基础范式
能证明排序、二分与分治算法。
- 给二分查找写循环不变量
- 用递推树分析归并排序
- 比较稳定性与原地性
A25 周 贪心与图算法
用交换论证和割性质处理最短路、生成树等问题。
- 证明活动选择的贪心选择性质
- 实现 BFS/DFS/Dijkstra/MST
- 为负权与非连通图构造反例
A35 周 动态规划与字符串
从状态、转移、边界和顺序构造 DP。
- 从暴搜递归提炼重叠子问题
- 实现背包、LCS 与区间 DP
- 比较滚动数组与完整恢复路径
A4长期 复杂性与工程验证
理解可计算性/NP 完全性入口，并用测试验证实现。
- 练习多项式归约的方向
- 构造随机/对抗/极限数据
- 维护证明—实现—测试三联记录
KNOWLEDGE MAP / 知识地图
概念、方法、练习和回忆锚点在同一张卡里
输入关键词或选择分类；按 / 可快速聚焦搜索，Esc 清空。
5 个知识节点
01方法
正确性证明与复杂度
算法答案由前置条件、后置条件和保持过程共同构成。
不变量归纳法递推式复杂度证明
CORE / 核心概念
- 初始化—保持—终止三段式
- 最坏、均摊、期望复杂度的假设
- 递归树、代换法与主定理
METHOD / 常用方法
- 先写命题量词和边界
- 用最小反例攻击证明
- 把实现行与证明步骤对应
PRACTICE / 练习
- 证明插入排序正确
- 求解三类分治递推式
- 给错误贪心策略构造反例
02范式
分治与贪心
分治拆独立子问题；贪心依赖可证明的局部选择安全性。
分治贪心交换论证归并选择
CORE / 核心概念
- 分解、递归求解与合并
- 最优子结构与贪心选择性质
- 交换论证、领先法与割性质
METHOD / 常用方法
- 先确认子问题是否独立
- 尝试替换最优解中的第一步
- 用反例区分直觉和定理
PRACTICE / 练习
- 实现归并排序和快速选择
- 证明区间调度策略
- 比较 Huffman 与错误合并规则
03图算法
遍历、最短路与生成树
图算法的核心是逐步扩大的已知区域以及跨越边界的安全选择。
BFSDFSDijkstraBellman-FordMST
CORE / 核心概念
- BFS 层次与 DFS 时间戳
- 松弛、最短路上界与负权边
- MST 割性质与 Kruskal/Prim
METHOD / 常用方法
- 明确定义当前已确定集合
- 每次松弛检查距离不增
- 按权重与图密度选择结构
PRACTICE / 练习
- 恢复 BFS 最短路径
- 构造 Dijkstra 负权反例
- 用两种 MST 算法交叉验证
04范式
动态规划
DP 是对状态空间的有序求值，不是背诵二维表。
动态规划状态转移背包区间DP
CORE / 核心概念
- 状态的充分性与无后效性
- 转移来源、边界和计算顺序
- 记忆化、递推、空间压缩与路径恢复
METHOD / 常用方法
- 从最后一步反推状态
- 先写指数递归再合并重复状态
- 用小输入列全状态验证转移
PRACTICE / 练习
- 实现 LCS 并恢复一个序列
- 设计 0/1 背包的一维更新顺序
- 为区间合并问题画依赖图
05边界
字符串算法与复杂性入口
模式匹配展示预处理如何复用信息；归约展示问题难度怎样传递。
KMPTrie后缀NP归约
CORE / 核心概念
- 前缀函数与失败转移
- Trie/自动机的状态复用
- P、NP、验证器与多项式归约
METHOD / 常用方法
- 维护最长 border 的语义
- 从已知困难问题归约到目标问题
- 严格检查归约方向和规模增长
PRACTICE / 练习
- 手算 KMP 前缀函数
- 实现 Trie 并统计内存
- 写一份 SAT 到简单问题的归约草图
没有匹配的知识节点
换一个更短的关键词，或清空分类后再试。
OUTPUT LAB / 练习与项目
用可交付作品检验理解
项目不是装饰：交付物、检查点与复盘记录缺一不可。
算法证明笔记库
每题保留模型、算法、证明、复杂度、反例和测试。
完成检查
- 证明使用完整量词
- 复杂度注明数据结构假设
- 失败思路也写入索引
图算法工具箱
统一图接口下的遍历、最短路、拓扑排序和 MST。
完成检查
- 支持断开图与大权值
- 与小规模穷举/第三方结果对拍
- 输出路径或证据而非只有数值
DP 状态设计展馆
至少 12 个问题的状态依赖图和滚动演示。
完成检查
- 每题解释状态充分性
- 标注边界和遍历顺序
- 至少一题恢复具体方案
REFERENCE SOURCES / 可核验资料
先读官方、大学与专业组织资料，再用高质量参考补齐
外部页面可能更新；课程顺序以本页路线为导航，资料以来源明确、可核验为优先。