算法设计方法：从递归到动态规划

0. 元信息

• 主题路径：docs/topics/algo-design/README.md
• 主分类：数据结构与算法
• 辅助分类：计算机基础
• 适合对象：掌握至少一门语言（Python 优先）、会写循环和函数、做过基础数据结构练习；想在面试、竞赛、工程面试题里独立设计算法的人
• 建议周期：8～12 周（每周 10～14 小时，含刷题、推导、复盘）
• 前置知识：Python 控制流、列表、字典、递归；高中数学基础（排列组合、等差等比）；lang-python 主题
• 最终目标：看到中等难度题（LeetCode Medium / Codeforces Div2 AC / AtCoder ABC DE），能在 30 分钟内写出状态转移或递归 + 剪枝的正确解，并解释复杂度

1. 学习路线

递归调用栈与终止条件
  → 回溯模板（排列 / 组合 / 子集）
  → 贪心：交换论证与反证
  → DP：状态、转移、初始化、压缩
  → 分治：归并、快排、最近点对
  → 状态机抽象：FSM 与 DP / BFS
  → 综合刷题与综合项目

每一步都是下一步的前置。贪心和 DP 都建立在递归思维上，分治和状态机把递归扩展到结构化场景。不要跳级刷题，先把范式想清楚。

2. 阶段周数分配

| 阶段 | 8 周方案 | 12 周方案 | 备注 | ||---:|---:|---| | 1. 递归与回溯 | 1 周 | 1.5 周 | 终止条件 + 调用栈图 | | 2. 贪心 | 1 周 | 1.5 周 | 区间调度、活动选择 | | 3. 动态规划 | 2 周 | 2.5 周 | 状态转移 + 滚动数组 | | 4. 分治 | 1 周 | 1.5 周 | 主定理 + 归并 / 快排 | | 5. 状态机 | 1 周 | 1.5 周 | FSM → DP / BFS | | 6. 综合刷题 + 项目 | 1 周 | 2 周 | 60~120 题 + 1 综合项目 | | 7. 复盘与模拟赛 | 1 周 | 1.5 周 | AtCoder / Codeforces |

8 周方案节奏紧，建议前 5 周固定 12 小时；12 周方案多出的时间做重做和重写。

3. 九阶段表

关键陷阱：贪心没证明就当 DP 解；DP 没画状态转移就硬写；分治忘了合并代价；状态机把”状态”和”动作”混在一起。

4. 第一周任务

Day 1 运行约定：使用 Python 3.10+。统一格式：python -X dev -W error -m py_compile foo.py 做静态检查；运行用 python foo.py < input.txt。代码风格 ruff 默认；测试用 pytest。所有题目代码统一放进 algo-design/week<N>/。

Day 7 步骤 A 把”状态 + 转移 + 初始化 + 输出 + 优化”五段写齐；步骤 B 每次只改一个输入维度。

5. 阶段通用验收

1. 不看答案独立重写核心代码；
2. 用自己的话解释该范式”解决什么问题、为什么有效、在哪类题里失效”；
3. 画一张图：递归树 / 状态转移表 / 分治递推式；
4. 测试空数据、最小值、最大值、异常输入；
5. 准备至少 3 组自定义数据并贴出实际输出；
6. 记录时间复杂度和空间复杂度（含每维含义）；
7. 能修改已有程序（加剪枝 / 改维度 / 换滚动数组），而不是只能照抄。

交付存放：第 3 项的图、第 5 项的输出、第 6 项的复杂度推导，统一存到 week<N>/notes/ 或 week<N>/<problem>/README.md。

6. 最终验收

• 独立实现：归并排序、快速排序（含 partition）、矩阵链乘、TSP 状压、编辑距离、N 皇后；

• 至少完成 80 道题（LeetCode / Codeforces / AtCoder），分布建议：

  子主题	题目数量	难度分布	平台建议
  递归与回溯	15 道	8 Easy + 5 Medium + 2 Hard	LeetCode
  贪心	12 道	6 Easy + 5 Medium + 1 Hard	LeetCode + Codeforces
  动态规划	25 道	5 Easy + 15 Medium + 5 Hard	LeetCode + AtCoder DP
  分治	10 道	4 Easy + 5 Medium + 1 Hard	LeetCode
  状态机	10 道	4 Easy + 5 Medium + 1 Hard	LeetCode
  综合	8 道	全部 Medium+	Codeforces / AtCoder

  约束：至少 25 道达到 Medium，至少 8 道达到 Hard / AtCoder 400+；动态规划题必须覆盖背包、序列、区间、状压四种类型。

• 完成 1 个综合 Python 项目（自带 README，能被他人按文档复现）；

• 能用 15 分钟讲清 5 种范式的适用场景、状态设计取舍和时间空间权衡。

7. 综合项目

首选：算法可视化桌面工具（必做：CLI 输入 + 输出 + 可选 GUI）。

• 输入：从 stdin 读取算法名（merge_sort / quick_sort / lcs / coin_change / n_queens）+ 数据集；
• 输出：必输出（1）算法过程的文字回放（每一步的状态、当前下标、做了什么操作）；（2）时间 / 空间复杂度与实际耗时；
• 算法：必须用至少 3 种范式（递归 + 分治 + DP）；
• 进阶可选：ASCII 动画（终端 / curses）、PyGame GUI、可对比两种算法的可视化。

备选：自动评测器。从 LeetCode / AtCoder 拉指定题目的测试用例，本地批量跑、对比时间、生成错题本。

备选：算法题模板生成器。给定题型关键词，输出 Python 模板代码（状态定义 / 转移 / 初始化 / 空间优化）。

任何项目都必须包含：

1. 需求说明；
2. 数据结构与算法选择理由；
3. 核心模块说明；
4. 模块化源码；
5. 边界测试；
6. 运行说明（Makefile 或清晰的 python 命令）；
7. README；
8. 复盘记录。

项目内交付物（设计/测试/复盘）随项目代码放在项目仓库的 notes/：design.md / test.md / retrospective.md。

8. 推荐开源资料

许可证提示：CLRS 与 Manber 自用学习合理引用；不要复制粘贴 CLRS 课后答案到公开仓库。LeetCode 题面版权见 LeetCode Terms of Service——代码自己写，思路可以分享。

默认使用顺序：先用 LeetCode 按 tag 刷 50 题建立手感 → 跑 AtCoder DP Contest 26 题 → 选读 CLRS 对应章节 → 周末打 Codeforces 模拟赛 → 写复盘到 notes/retrospective.md。

9. 学习资料汇聚（v0.3 自包含）

本节由本计划生成。链接指向原始材料或作者公开内容。竞赛平台和题库持续更新，记录时务必写明题目 ID 与比赛日期。

9.1 背景与动机

算法设计方法这门学问成型于 1960 年代末到 1990 年代初。Faigle、Karp、Tarjan 把”整数规划 + 组合”系统化；Bellman 在 1950 年代提出动态规划；Dijkstra、Huffman、Krusal、Prim 把贪心写成可证明的最优解；Knuth 在 TAOCP 里把基础范式和具体算法都做了工程化整理。Cormen、Leiserson、Rivest、Stein 在 1990 年的 CLRS 把这些范式组织成教学体系。

行业位置：算法面试是 FAANG 及国内大厂标配；竞赛选手（Codeforces 红名 / AtCoder 橙名以上）通常对范式切换非常熟练；工程界对算法的需求集中在”用对结构 + 不写明显低效代码”。一句话总结：算法范式决定你能不能把问题抽象出来，编程能力决定你能不能写对实现，两者缺一不可。

9.2 概念地图

核心概念（≥10）：

flowchart TB
    Recursion[递归调用栈]
    Backtrack[回溯与剪枝]
    Greedy[贪心 + 交换论证]
    DP[动态规划]
    DivideConquer[分治]
    FSM[有限状态机]
    Memo[memoization / 滚动数组]
    Order[拓扑序 / BFS]
    Recurrence[递推式 + 主定理]
    Permutation[排列 / 组合 / 子集]
    Knapsack[背包 / 序列 / 区间 / 状压]

    Recursion --> Backtrack
    Recursion --> DivideConquer
    Recursion --> Memo
    Memo --> DP
    Backtrack --> Permutation
    Greedy --> DP
    DivideConquer --> Recurrence
    FSM --> DP
    FSM --> Order
    DP --> Knapsack

关系说明：

• 递归是底座：回溯、分治、memoization DP 都需要递归；
• DP 由”递归 + 状态去重”演化而来，贪心是 DP 在”每步只看局部最优且能证明不破坏全局”下的特例；
• 分治与 DP 的区别：分治的子问题互不重叠（merge sort），DP 的子问题可能重叠（LCS）；
• 状态机思维把”问题当前所处的状态”显式抽象出来，可写成 DP 或 BFS 拓扑序。

9.3 基础知识讲解

9.3.1 经典论文

9.3.2 经典书籍

重点读这 5 本。每本都跟一个练习集。

备查：Knuth TAOCP 当字典；Sedgewick 的 Algorithms 当 Java/C++ 实现对照；Halim 的 Competitive Programming 3 当竞赛书。

9.3.3 优秀博客

9.3.4 核心人物

9.3.5 开发方法

9.3.6 重点训练材料（按用途分组）

• AtCoder Educational DP Contest（A~Z，共 26 题）：DP 入门到进阶路线图。
• AtCoder ABC/ARC/AGC 题库：每周免费比赛；赛后官方 Editorial。
• Codeforces Round（含 Div.1+2 / Div.2 / Div.3 / Educational）：每场 5~7 题，难度分级清晰。
• LeetCode Top Interview 150 / Hot 100：面试导向，类型分布好。
• Petrozavodsk Camp 题库（按年份）：高级训练营，难度偏高。

9.4 经典问题与经典案例

9.5 学习难点

概念难点

思维难点

工程难点

9.6 技术标准与接口

9.6.1 Entity

9.6.2 Scope

• CLRS / TAOCP 给出算法范式与正确性证明；不教语言实现细节。
• AtCoder DP Contest 是 26 题固定训练集，覆盖 DP 所有典型子类型。
• LeetCode 按题型标签和公司标签分类；题面用 ToS 管理。
• Codeforces Round 模拟真实比赛节奏；Editorial 由官方出题人或社区维护。
• 算法可视化工具（Algorithm Visualizer、VisuAlgo）是辅助理解手段，不是答案来源。

9.6.3 Structure

• CLRS 章节结构：Part I Foundations（Part 1~5）、Part II Sorting and Order Statistics、Part III Data Structures、Part IV Advanced Design and Analysis、Part V Advanced Data Structures、Part VI Graph Algorithms、Part VII Selected Topics。
• AtCoder DP Contest 26 题：AC 入门、DF 基础、GM 进阶、NZ 高级与状压。
• Codeforces Round 一场 5~7 题：Div.2 A/B 是 Easy、C/D 是 Medium、E/F 是 Hard。
• 必须掌握的方法：写递归 → 写 memoization → 改 DP → 优化空间；构造反例；画状态转移图；用 Master Theorem 验 T(n)。

9.6.4 Ecosystem

• 实现语言：Python（简洁）、C++（性能与 STL）、Java（工程）。本计划优先 Python，关键 DP 与状压给 C++ 对照。
• 工具：itertools（排列组合）、functools.lru_cache（memoization）、heapq（Huffman / Dijkstra）、collections.deque（BFS）、bisect（LIS 优化）、sys.setrecursionlimit（深递归）。
• 在线评测：LeetCode Playground、AtCoder 自定义测试、Codeforces 提交 + Hack 机制。
• 训练平台：USACO Guide、Codeforces Gym、CSES Problem Set（按章节分类）。

9.6.5 Depth Tiers

本父主题目标是 L3。状态机与高级 DP 可触及局部 L4，但不作为 8～12 周的硬门槛。

9.6.6 Source

• CLRS 官网：第 4 版目录与勘误。
• AtCoder Educational DP Contest：26 题题面 + Editorial。
• Codeforces：Round 题库与 Editorial。
• CP-Algorithms：社区维护的算法百科。
• 引用版本快照日期：2026-07-30。题库会更新，引用时务必写明题号 / Round 号。

10. 常见误区

• 把”看完视频/书”当成会做；不写代码不刷题；
• 跳过递归直接学 DP，写出来的状态转移无根；
• 贪心题不证明正确性，凭感觉出答案，遇到边界就崩；
• DP 状态多了一维或漏了一维，靠调试发现；
• 分治忘了合并代价，把 O(n log n) 写成 O(n)；
• 状态机把”状态”和”动作”混在一起，转移图画不清楚；
• 刷题只刷 Easy，从来不碰 Medium / Hard；
• 错题不复盘，下次遇到同类型还是不会；
• 只看 Editorial 不自己重写，比赛时仍不会；
• 评测 TLE 不分析复杂度，反复试不同常数；
• Python 递归深度超 1000 直接放弃，不知道 setrecursionlimit；
• 把 ACM / OI 风格的输入输出格式当 LeetCode 题用，写复杂 I/O；
• 把”打比赛”当成唯一训练方式，忽略工程化项目；
• 学完不复盘，下次面试/比赛依然答不上来。

11. 所有知识点分类（统一规则）

1. 编程语言
2. 数据结构与算法
3. 计算机基础
4. 工程技术
5. Web 与后端
6. 前端与客户端
7. 数据与人工智能
8. 项目与职业能力
9. 安全与可靠性

本计划归属：数据结构与算法 主 + 计算机基础 辅。