OI Wiki 学习地图 · 第 5 章 进阶路径三:动态规划与字符串

OI Wiki 学习地图 · 第 5 章 进阶路径三:动态规划与字符串

章节摘要:本章讲动态规划(docs/dp/ 22篇)与字符串(docs/string/ 22篇)。DP 从入门(背包)到进阶(区间/树形/状压),字符串从 KMP 到 AC自动机。SAM 后缀自动机 docs/string/sam.md 是本章难点(★),做慢节奏精讲(endpos等价类/parent tree/在线构建算法)。本章共 3 节,前置依赖为第 1-4 章。

路径坐标

进阶(本章) → 省选(状压DP/插头DP 第7章)

学习目标

1. 掌握 DP 基础(背包/线性/区间)。
2. 掌握树形 DP 与状压 DP。
3. 掌握 KMP/AC自动机/Trie。
4. 理解 SAM 后缀自动机(★)。

子章节导航

01 动态规划(对应 docs/dp/)

DP入门(背包01/完全/多重);线性DP(LIS/LCS);区间DP(石子合并);树形DP(没有上司的舞会);数位DP;状压DP(旅行商);记忆化搜索;引用 docs/dp/ 各页。

02 字符串基础(对应 docs/string/)

字符串哈希;KMP(next数组/匹配);Trie字典树;AC自动机(Trie+KMP fail指针);马拉车Manacher;后缀数组SA;引用 docs/string/ 基础页。

03 SAM后缀自动机难点精讲 ★

SAM docs/string/sam.md(endpos结束位置集合/等价类/parent tree后缀链接/在线构建算法O(n)/应用:子串计数/最长公共子串/第k小子串);为什么SAM难(多概念交织);慢节奏精讲构建算法;与后缀数组SA对比;广义SAM多串。

前置知识与后续延伸

前置:第1-4章。后续:第6章数学(生成函数与DP);第7章(插头DP是状压DP进阶)。