动态规划Dynamic programming
保存子问题结果，按依赖组合出更大问题的解。
- 核心约束
- 状态定义与转移必须覆盖合法解并保持语义一致。
- 适用问题
- 重叠子问题、序列比较与优化问题。
- 边界与取舍
- 状态空间可能很大，必须明确边界与依赖顺序。
时间与空间#
S 为实际计算的状态数，T 为平均每状态转移工作；并非所有问题都拥有相同 S 和 T。
- 时间成本
- ，另计状态排序或预处理
- 空间成本
- 常见表格 / 记忆化 ；滚动数组取决于依赖范围
先定义状态、转移、边界和合法计算顺序；重复子问题只算一次。背包 依赖容量数值 W，是伪多项式界，不是关于输入位数的多项式。
工程中的应用#
1 个案例 · 附源码PostgreSQL 按参与连接的关系数量逐层生成候选，把同一关系集合的路径归入同一 RelOptInfo，复用已经分析的子问题。
附源码片段 · 图处理与编译
基础原理参考资料
MIT 6.006 · Dynamic Programming, SRTBOT按子问题、关系、拓扑顺序、边界、原问题和时间组织 DP 分析。