动态规划导览
动态规划导览
动态规划不是套用数组维度，而是在状态 DAG 上保存足以影响未来的信息。本页连接已经整理完成的新笔记；旧版提纲与尚未重写的专题仍保留在归档中。
推荐路线
线性状态 → 序列对齐 → LIS 模型与题型 → 区间状态。阅读时优先追问“状态为什么封闭”和“最后一步怎样划分决策”。
从这里开始
- 线性状态动态规划：认识自然处理顺序、状态含义与常见转移结构；
- 单调队列优化DP模型：从候选集合的单向移动出发，识别可被窗口最值压缩的 DP 转移；
- 序列对齐 DP：从双前缀状态理解 LCS、编辑距离与局部匹配；
- LIS 模型：整理最长上升子序列的状态设计与优化；
- LIS 题型：从显式顺序、偏序和链覆盖识别模型；
- 区间 DP：通过最后一步决策把连续区间拆成独立子问题。
- 树上背包模型：从孩子独立、资源拆分到接口状态与结构变换，识别树上的分组背包。
近期推荐
-
P3052 Cows in a Skyscraper：从枚举一整趟的子集，压缩到只记录趟数与最后一趟载重；
-
P2679 子串：补上“当前位置是否仍连接当前段”，让分段计数状态保持封闭；
-
P3047 Nearby Cows：把小半径距离球压成距离前缀，并用换根转移补入父侧信息；
-
P4302 字符串折叠：从区间最终形态出发，统一处理拼接与周期压缩；
-
P4363 一双木棋：把棋盘压成合法轮廓，在状态图上进行极大极小搜索。
更多案例
-
ABC457G：将时空可达关系转化为二维偏序，再归约到最长下降子序列；
-
P1450 硬币购物：先用完全背包预处理无限制方案，再用容斥排除超限情况；
-
[[200_Publish/260_Records/DP/P1613 跑路]]：用布尔关系倍增压缩路径长度，再在新图上求最少操作次数。
旧笔记与后续方向
旧版动态规划提纲、背包与树图 DP 暂时收纳在 旧版动态规划索引。它们仍可查阅，但不再作为当前学习路线的主入口。
状态压缩与树形 DP 已先接入单题案例；计数 DP、数位 DP 和决策优化会在形成完整专题后逐步接回本页。