动态规划

约 162 个字 预计阅读时间 1 分钟

动态规划原理

最优子结构

最优子结构性质：问题的最优解由相关子问题的最优解组合而成，而这些子问题可以独立求解。

重叠子问题

适合用动态规划方法求解的最优化问题应该具备的第二个性质是子问题空间必须足够小，即问题的递归算法会反复求解相同的子问题，而不是一直生成新的子问题。

如果递归算法反复求解相同的子问题，我们就称最优化问题具有重叠子问题性质。

---

最后更新: 2024年4月20日 22:02:37
创建日期: 2024年4月20日 22:02:37