贪心与动态规划：从区间调度到状态转移方程

0. 元信息

• 主题路径：docs/topics/algo-design/subtopics/greedy-and-dp/README.md
• 父主题：algo-design
• 主分类：数据结构与算法
• 辅助分类：计算机基础
• 适合对象：掌握递归与回溯、Python 基础数据结构；想系统性建立贪心和 DP 设计能力的学习者
• 建议周期：3～4 周（每周 10～14 小时）
• 前置知识：recursion-and-backtracking、高中数学（递推、求和）、基本复杂度分析
• 最终目标：能在 35 分钟内独立设计 0/1 背包、LIS、LCS、矩阵链乘的状态与转移；能用一句话证明常见贪心题的正确性或构造反例推翻

1. 学习路线

贪心范式：排序后扫描 + 交换论证
  → 区间调度 / Huffman / 跳跃游戏
  → DP 范式：递归 + memoization
  → 自顶向下 vs 自底向上
  → 0/1 背包 → 完全背包 → 多重背包
  → 序列 DP：LIS / LCS / 编辑距离
  → 区间 DP：矩阵链乘 / 戳气球
  → 状压 DP：TSP / 集合划分
  → 空间优化：滚动数组 / 状态压缩

每一步都跟一道题。贪心要先写 DP，再构造反例；DP 先写二维，再压一维。

2. 阶段周数分配

每天 1.5～2 小时。3 周方案聚焦前 5 阶段；4 周方案多一周做综合刷题与空间优化。

3. 九阶段表（精简）

3.1 核心知识

• 贪心：每步取局部最优，能证明全局最优；不能证明时退到 DP。
• DP 三要素：状态定义、转移方程、初始化（含边界）。
• DP 优化方向：去掉无效维度、滚动数组、单调队列 / 单调栈。
• 0/1 背包 vs 完全背包：状态相同，转移遍历顺序不同（0/1 逆序、完全背包正序）。
• 序列 DP：状态维度常是下标 i 与 j；LIS 用 patience sorting 可达 O(n log n)。
• 区间 DP：状态维度是区间 [l, r]；从小到大枚举区间长度。
• 状压 DP：用 bitmask 表示集合；n ≤ 20 比较合适。

3.2 实践产出

• 8 道贪心（435 无重叠区间、253 会议室 II、55 跳跃游戏、45 跳跃游戏 II、134 加油站、406 根据身高重建队列、621 任务调度器、763 划分字母区间）；
• 25 道 DP，含：
  • 5 道入门（70 爬楼梯、198 打家劫舍、64 最小路径和、322 零钱兑换、300 LIS）；
  • 8 道基础（416 分割等和子集、494 目标和、518 零钱兑换 II、1143 LCS、72 编辑距离、5 最长回文子串、516 最长回文子序列、647 回文子串）；
  • 6 道区间 DP（312 戳气球、1039 多边形三角剖分、1547 切棍子的最小成本、1000 合并石头的最低成本、1771 由子序列构造的最长回文、1312 字符串构造）；
  • 6 道状压 DP（464 我能赢吗、526 优美的排列、847 访问所有节点的最短路径、1434 每个人戴不同帽子的方式、1799 N 次操作后的最大分数、1349 参加考试的最大学生数）。

3.3 可观察学会标准

• 不看答案在 25 分钟内写出 0/1 背包的状态转移；
• 能在 10 分钟内构造 435 / 55 / 134 等题的反例（如果是错题）；
• 能独立推导 312 戳气球的状态维度 dp[l][r]；
• 能解释为什么 TSP 状压用 dp[mask][i] 而不是 dp[mask]。

4. 第一周（每天 1.5~2 小时）

Day 1 约定：本计划使用 Python 3.10+。统一格式：python -X dev -W error -m py_compile foo.py；测试用 pytest；题号统一以 LeetCode 编号为准。所有代码放进 algo-design/greedy-dp/week<N>/ 目录；每个题目单独 .py 文件，配套 notes/<problem>.md 含状态转移方程、复杂度推导、反例构造（贪心题）。

Day 7 执行次序

步骤 A —— LPS 完整版（60~90 分钟）

1. 写暴力递归 lps(s, i, j)；
2. 加 memo → 自顶向下 DP；
3. 改自底向上二维 DP dp[i][j]；
4. 压一维滚动数组；
5. 对比四版耗时。

步骤 B —— 4 类边界用例（30~45 分钟）

Day 7 当天必完成步骤 A；步骤 B 至少完成 B1、B3。

5. 阶段通用验收（精简）

1. 不看答案重写 25 道 DP 模板；
2. 用自己的话解释贪心和 DP 的适用边界；
3. 画出每道 DP 题的状态转移表（二维表填 3×3）；
4. 测试空数据、单元素、相同元素、相反元素四档；
5. 至少准备 3 组自定义数据贴出实际输出；
6. 记录每题时间空间复杂度，并指出哪一维能压缩；
7. 能给现有 DP 加维度（如加一维费用）或压维度（如二维 → 一维）。

6. 最终验收

• 独立实现：25 道 DP（5 入门 + 8 基础 + 6 区间 + 6 状压）+ 8 道贪心（含 Huffman、活动选择、Jump Game）；

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

  子阶段	题目数量	难度分布	平台建议
  贪心基础	8 道	4 Easy + 3 Medium + 1 Hard	LeetCode 435 / 253 / 55 / 45 / 134 / 406 / 621 / 763
  DP 入门	5 道	4 Easy + 1 Medium	LeetCode 70 / 198 / 64 / 322 / 300
  0/1 背包与完全背包	4 道	1 Easy + 3 Medium	LeetCode 416 / 494 / 518 / 474
  序列 DP	8 道	2 Easy + 5 Medium + 1 Hard	LeetCode 1143 / 72 / 5 / 516 / 647 + 3 进阶
  区间 DP	6 道	1 Easy + 4 Medium + 1 Hard	LeetCode 312 / 1039 / 1547 / 1000 / 1771 / 1312
  状压 DP	6 道	1 Easy + 4 Medium + 1 Hard	LeetCode 464 / 526 / 847 / 1434 / 1799 / 1349

  约束：至少 12 道达到 Medium，至少 5 道达到 Hard / AtCoder 400+；DP 题必须覆盖背包、序列、区间、状压四种类型。

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

• 能用 15 分钟讲清贪心证明三件套（交换论证 / 反例构造 / 拟阵）、DP 三要素、0/1 vs 完全背包遍历顺序、滚动数组方向、状压状态数估算 n × 2^n。

7. 综合项目

首选：算法可视化桌面工具（必做：CLI 输入 + 输出 + 可选 GUI）。
备选：自动评测器（从 LeetCode / AtCoder 拉指定题目的测试用例，本地批量跑、对比时间、生成错题本）。
备选：算法题模板生成器（给定题型关键词 → 输出 Python 模板：状态定义 / 转移 / 初始化 / 空间优化）。

算法可视化工具必做要求：

• 输入：stdin 接收算法名（merge_sort / quick_sort / lcs / coin_change / n_queens / tsp）+ 数据集；
• 输出：必输出（1）算法过程的文字回放（每一步状态、当前下标、做了什么操作）；（2）时间 / 空间复杂度 + 实际耗时；（3）解的总数 / 解集；（4）状态转移表（二维 DP 填表过程）；
• 算法：必须用至少 3 种范式（递归 + 分治 + DP 或贪心 + DP + 状压）；
• 进阶可选：ASCII 动画（终端 curses 逐步展开）、PyGame GUI、可对比两种算法的可视化（如 DFS vs 贪心）。

任何综合项目都必须包含：

1. 需求说明（含输入输出约定）；
2. 数据结构与算法选择理由（为何用 DP、为何选这种状态）；
3. 核心模块说明（Solver / Recorder / Renderer 三层）；
4. 模块化源码（每题单独文件 + 公共 base class）；
5. 边界测试（n=0, 1, 2, 8, 10 + 空数据 + 极端数据）；
6. 运行说明（Makefile 或清晰的 python -m 命令）；
7. README（项目介绍、运行步骤、目录结构、复盘）；
8. notes/ 规范：

本主题贡献

3 职责

1. 给出可证明的贪心策略 —— 区间调度按”结束时间”排序（活动选择）、跳跃游戏维护”最远可达下标”、Huffman 用优先队列每次合并最小两个；并能用交换论证（找等价代换的”反序对”）或拟阵（独立集 + 交换性质）证明正确性，不能证则必须退到 DP。
2. 把 DP 拆成三要素 —— 状态定义（“做完第 i 步还剩什么”）、转移方程（前驱状态 + 当前一步的递推）、初始化（含 dp[0] 与 dp[i][0] 边界）；并在二维 → 一维滚动数组时画箭头验”旧值不被新值覆盖”。
3. 用状态压缩处理维度爆炸 —— 0/1 背包 vs 完全背包的遍历方向（0/1 逆序、完全背包正序）、LIS 用 patience sorting 压到 O(n log n) 单调栈、TSP 状压用 dp[mask][i] 估算 n × 2^n 状态数。

4 交付物

1. 33 道题解（25 DP + 8 贪心）+ 4 类边界用例日志（空 / 单元素 / 全相同 / 全相反）。
2. 算法可视化工具（CLI → DP 填表过程 + 贪心 vs DP 反例对比 + 状态转移表二维填表截图）。
3. 至少 5 道 DP 题的二维状态转移表（70 爬楼梯 / 198 打家劫舍 / 322 零钱兑换 / 1143 LCS / 72 编辑距离）落 notes/state-tables/ + 至少 3 道疑似贪心题的反例构造（含输入 → 反例 → 错误输出）落 notes/greedy-counters/。
4. DP 模板 5 件套（0/1 背包 / 序列 DP / 区间 DP / 状压 DP / 滚动数组）落 notes/dp-templates/，每个模板标明”遍历方向”与”压缩维度”。

3 指标

1. 35 分钟内独立设计 0/1 背包 / LIS / LCS / 矩阵链乘的状态与转移（覆盖背包、序列、区间、状压四大 DP 范式）。
2. 10 分钟内构造 435 / 55 / 134 等疑似贪心题的反例（证明”贪心不是万能”已固化为本能 —— 任何贪心策略先问一句”什么时候会反例”）。
3. 二维 dp 压一维后内存下降 ≥ 50%（验证空间优化方向正确；如 198 打家劫舍 O(1) 滚动变量比 O(n) 数组内存少一半）。

许可证提示：CLRS 与 Manber 自用学习合理引用；不要复制粘贴 CLRS 课后答案到公开仓库。LeetCode 题面版权见 LeetCode Terms of Service——代码自己写，思路可以分享。CP-Algorithms 是 CC BY-SA。默认做法是读思路后自己重写代码，而不是复制 Editorial。

默认使用顺序：先用 LeetCode 按 tag 刷 30 道建立手感 → 跑 AtCoder Educational DP Contest 26 题 → 选读 CLRS 第 1516 章（DP / 贪心）→ 周末打 Codeforces 模拟赛 → 选读 Manber 第 12 章做归纳思维训练 → 用 labuladong / CP-Algorithms 对照 5 道卡住的题 → 写复盘到 notes/retrospective.md。

8. 推荐开源资料

许可证提示：CLRS 与 Manber 自用学习合理引用；不要复制粘贴 CLRS 课后答案到公开仓库。LeetCode 题面版权见 LeetCode Terms of Service——代码自己写，思路可以分享。CP-Algorithms 是 CC BY-SA。默认做法是读思路后自己重写代码，而不是复制 Editorial。

默认使用顺序：先用 LeetCode 按 tag 刷 30 道建立手感 → 跑 AtCoder Educational DP Contest 26 题 → 选读 CLRS 第 1516 章（DP / 贪心）→ 周末打 Codeforces 模拟赛 → 选读 Manber 第 12 章做归纳思维训练 → 用 labuladong / CP-Algorithms 对照 5 道卡住的题 → 写复盘到 notes/retrospective.md。

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

9.1 背景与动机

Bellman 在 1954 年的 RAND 报告中命名 Dynamic Programming（为避开”研究”在政府语境里的敏感词）。同一时期，Dijkstra、Huffman、Kruskal 把”每步取局部最优”的贪心方法系统化。Cormen 等人在 1990 年的 CLRS 把这两类范式放进了同一本教材并标准化了”状态 / 转移 / 初始化”的写作格式。

行业位置：DP 是中高级面试必考（LeetCode Medium 中 DP 占 1/3）；贪心是面试”加分题”（能证明正确性显得有深度）。竞赛里 DP 是 Codeforces Div.2 D/E 题常见类型。一句话总结：贪心 = DP 在”每步只看局部最优且不破坏全局”的特例；DP 是带记忆的递归。

9.2 概念地图

flowchart LR
  Greedy[贪心]
  SwapArg[交换论证]
  CounterEx[反例构造]
  DP[动态规划]
  State[状态定义]
  Trans[转移方程]
  Init[初始化]
  Opt[空间优化]
  Knapsack[0/1 背包]
  Sequence[序列 DP]
  Interval[区间 DP]
  Bitmask[状压 DP]

  Greedy --> SwapArg
  Greedy --> CounterEx
  Greedy --> DP
  DP --> State
  State --> Trans
  Trans --> Init
  DP --> Opt
  Opt --> Knapsack
  Opt --> Sequence
  Opt --> Interval
  Opt --> Bitmask

核心关系：贪心要先证明（交换论证）或找反例，否则退到 DP；DP 三要素是状态、转移、初始化；空间优化是工程化必经步骤。

9.3 基础知识讲解

9.3.1 经典论文

9.3.2 经典书籍

9.3.3 优秀博客

9.3.4 核心人物

9.3.5 开发方法

9.4 经典问题与经典案例

9.5 学习难点

概念难点

思维难点

工程难点

9.6 技术标准与接口

9.6.1 Entity

9.6.2 Scope

• DP 适用：最优化、计数、存在性三类问题；状态空间可枚举。
• 贪心适用：区间调度、Huffman、活动选择、单调队列、跳跃游戏。
• 不适用：图最短路（用 BFS / Dijkstra）；最大流（Ford-Fulkerson）；NP-hard 无多项式解。

9.6.3 Structure

• DP 三要素：状态定义、转移方程、初始化（含 dp[0]、dp[边界]）。
• 空间优化方向：滚动数组（去掉一维）、单调队列（优化转移）、位运算压缩状态。
• 必须掌握的方法：暴力递归 → 加 memo → 自底向上；画转移图；填 3×3 表验正确性。

9.6.4 Ecosystem

• 工具：functools.lru_cache（memoization）、bisect（LIS 优化）、heapq（Huffman）、array.array（节省内存）。
• 在线评测：LeetCode、AtCoder、Codeforces、CSES。
• 训练集：AtCoder Educational DP Contest、USACO Guide DP 模块、CSES DP 章节。

9.6.5 Depth Tiers

本子主题目标：L3。能独立设计状态转移 + 空间优化 + 给出贪心证明即达到。

9.6.6 Source

• AtCoder Educational DP Contest：26 题题面 + Editorial。
• CLRS 官网：第 4 版目录与勘误。
• CP-Algorithms DP：社区算法百科。
• 引用版本快照日期：2026-07-30。题号稳定，Editorial 持续更新。

10. 常见误区

• 贪心题不证明正确性，遇到反例就 WA；
• DP 状态多了一维或漏了一维，靠调试发现；
• 0/1 背包写错遍历顺序（该逆序写成了正序）；
• 完全背包写错遍历顺序（该正序写成了逆序）；
• 滚动数组时方向写反，旧值被覆盖；
• 区间 DP 把 l / r 的开闭写错（< vs <=）；
• 状压 DP 没算状态数就开 2^25；
• 贪心选错排序键（如按起始时间排而不是结束时间）；
• 初始化 dp 数组忘了设 INF 或 dp[0]；
• 把”求方案数”和”求最优解”的 DP 模板混用；
• DP 写出来发现是”递归 + 备忘录”但复杂度仍是指数（没去重）；
• 复杂度算错，把 O(n²) 当 O(n log n)；
• 写完不复盘，下周遇到同类型还是不会。

11. 所有知识点分类

1. 编程语言（辅）：Python 列表 / 元组 / 字典、functools.lru_cache 自顶向下 memo、bisect 做 LIS 优化、heapq 做 Huffman / 优先队列、array.array 节省内存。
2. 数据结构与算法（主）：贪心（交换论证 + 反例构造）、DP 三要素（状态 / 转移 / 初始化）、0/1 背包 / 完全背包 / 多重背包、序列 DP（LIS / LCS / 编辑距离 / 回文）、区间 DP（戳气球 / 矩阵链乘）、状压 DP（TSP / 优美排列）、空间优化（滚动数组 / 单调队列 / 位运算）。
3. 计算机基础：递推与求和、最优性原理、拟阵理论（贪心适用条件）、P/NP 问题分类。
4. 工程技术：复杂度推导（T(n)）、画 3×3 状态转移表、箭头法判断滚动方向、n × 2^n 状态数估算、用 numpy / array.array 控内存。
5. Web 与后端：无直接关联。
6. 前端与客户端：无直接关联。
7. 数据与人工智能：无直接关联（DP 可用于序列标注 / 隐马尔可夫，但本计划不展开）。
8. 项目与职业能力：AtCoder Educational DP Contest 26 题训练路径、LeetCode 中高级面试 DP 题（Medium 中占 1/3）、35 分钟独立设计状态转移、10 分钟构造贪心反例。

本计划归属：数据结构与算法 主 + 编程语言 辅。