DP 简介及基本知识

动态规划（Dynamic Programming, DP） 是一种将复杂的问题分解为简单子问题的方式来解决问题的方法。

动态规划中主要由两个部分组成：一为状态，二为转移。状态和转移就组成了一个有向的状态转移图。动态规划需要满足有拓扑序（当拓扑序不知道但有，可以考虑拓扑排序，找到拓扑序，或者记忆化搜索），即状态转移图为一个有向无环图。另外，DP 数组里只记录最优状态，不能一个非最优状态转移后的答案比一个最优状态转移后答案还有，这叫作最优子结构性质。

所以在我们设计状态转移时，就需要考虑以上两点。

DP 并不是一种具体的算法，而是一种解决问题的思路、方法。因此动态规划是比较难的，因为它可以和其他很多算法结合，如各种优化 DP 等。