动态规划 · 相关章节

算法是 CSP-S 复赛的"兵器库"。本章按"思想 → 模板 → 真题"组织，覆盖排序、二分、前缀和、双指针、倍增、分治、搜索、贪心、动态规划、字符串进阶与图论进阶。每个知识点都给出可直接抄写的 C++17 模板。

考核目标：掌握动态规划的核心思想（最优子结构、重叠子问题、状态转移方程、边界条件）；能使用代码解决一维动态规划问题（如斐波那契、爬楼梯、最大子数组和）与简单背包问题（0/1 背包、完全背包）。

复杂动态规划是在基础一维动态规划之上的扩展，主要包括二维动态规划及动态规划最值优化策略。二维动态规划通过二维状态数组描述问题，适用于处理具有两个维度约束的场景（如矩阵路径、区间问题等）；最值优化则通过对状态转移方程的分析，减少冗余计算，提升算法效率。