动态规划部分简介

本章将介绍介绍动态规划(Dynamic Programming, DP)及其解决的问题、根据其设计的算法及优化。

动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

由于动态规划并不是某种具体的算法,而是一种解决特定问题的方法,因此它会出现在各式各样的数据结构中,与之相关的题目种类也更为繁杂。

在 OI 中,计数等非最优化问题的递推解法也常被不规范地称作 DP,因此本章将它们一并列出。事实上,动态规划与其它类型的递推的确有很多相似之处,学习时可以注意它们之间的异同。

参考资料

动态规划 - 维基百科,自由的百科全书


评论