动态规划基础
动态规划（Dynamic Programming，DP）是算法世界里最「值得投资」的一类思想——它不是某一个具体算法，而是一套把大问题拆成语义相同的小问题、再合并小问题的解得到大问题解的方法论。其核心抓住两个特征：最优子结构（大问题的最优解由子问题的最优解构成）和重叠子问题（子问题会被反复求解）。只要一个最优化问题同时满足这两点，用 DP 配合「记忆化」或「递推填表」就能把指数级暴力搜索压到多项式时间，效率提升常常是质变级别的（O(2ⁿ) → O(n²)）。
DP 的全部考点都源于一个心智模型：用「状态」描述子问题、用「状态转移方程」描述子问题之间的关系。由此衍生出三大主题：①DP 的三要素与两种实现（状态定义 / 转移方程 / 边界条件；自顶向下记忆化 vs 自底向上递推）；②入门经典模型（斐波那契、爬楼梯、打家劫舍——一维线性递推）；③背包与零钱家族（0-1 背包的「选或不选」、完全背包的「无限件」、零钱兑换的「组合数/最少硬币数」）。其中0-1 背包是 DP 的「Hello World」，**空间优化（二维压一维）**体现倒序遍历的精妙，完全背包仅靠把倒序改正序就完成了语义切换——它们本质都是「状态定义 + 转移方程 + 计算顺序」三件套的反复练习。本叶是 DP 三部曲（基础 → 序列区间 → 进阶）的开篇，吃透这里的模型与套路，后续 LCS/LIS/编辑距离、树 DP、数位 DP 才有根基。
评价
优点
- 指数级降多项式：暴力递归 O(2ⁿ) 的重叠子问题，加记忆化或递推后降到 O(n)、O(n²)，常常是质变——这是 DP 区别于分治、贪心的核心价值
- 最优解的万能解：只要问题有「最优子结构 + 重叠子问题」，DP 几乎一定能给最优解，不像贪心需要严格的局部最优可推出全局最优
- 状态即答案：定义好状态和转移方程后，代码高度模板化（二维数组 + 两层 for + 一个 max/min），可复用性极强
- 可扩展性强：同一套状态/转移框架，加一维状态、改一个转移就能解决变体（0-1 背包 → 完全背包 → 多重背包 → 分组背包）
缺点
- 状态定义靠经验：DP 最难的是「怎么定义状态」和「怎么找转移方程」，没有通用算法，强依赖题感和模型积累——这是新手最大的拦路虎
- 空间常偏大：典型 DP 表是 O(n²) 甚至 O(n³) 空间，大规模输入易爆内存（需空间优化技巧：滚动数组、一维化）
- 常数大、不一定是实战最快：DP 的常数因子往往比贪心、二分大；工程里若贪心可用优先用贪心，DP 是「保底解」
- 维度爆炸：状态空间随约束维度指数增长（背包加「件数限制」「组数」等维度后，状态数迅速失控）
本叶地图
- 入门 —— DP 核心思想、与分治/贪心的区别、三要素、记忆化 vs 递推、斐波那契入门
- 背包问题与零钱兑换 —— 0-1 背包（二维→一维倒序）、完全背包（正序）、零钱兑换组合数与最少硬币数
- DP 设计方法与常见模型 —— 设计五步、爬楼梯、打家劫舍、Kadane 最大子数组和、如何识别 DP 题
- 参考 —— DP 三要素速查、常见模型表、背包代码模板、易错点清单
交互演示
- 0-1 背包可视化演示 —— 状态转移表的逐格填充
- 完全背包可视化演示 —— 物品无限件的正序填充
- 零钱兑换可视化演示 —— 组合数与最少硬币数