动态规划

动态规划（Dynamic Programming, DP），一般简称DP

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

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

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