浅谈状态空间：https://www.cnblogs.com/AKMer/p/9622590.html
所谓(DP)，就是(Dynamic) (programming)，动态规划算法。
(OI)中大部分问题的本质是解决对状态空间的遍历以及处理，而(DP)则是针对某一类满足特定条件的问题，对状态空间进行分阶段、有顺序，无重复、决策性的遍历求解。
(DP)把原问题视作若干个重复的子问题逐渐递进，每个子问题都构成一个“阶段”，在完成前一个阶段的计算后，才会进行对下一个阶段的计算。想要熟练掌握(DP)，需要擅长于将问题与状态空间进行类比，并且擅长于找到合适的遍历状态空间的方式，优化状态空间的维度。
对状态空间的遍历就像是对一张有向无环图的拓扑遍历一样，节点对应状态，边对应转移， 转移的选取就是决策。在阶段计算完之后，每个节点上都只会保留与最终解相关的信息，这就是(DP)。
图由点集和边集构成，而(DP)的三要素则是状态和转移，以及决策。
子问题重复性：各个阶段的子问题一样，用一个固定的公式去计算，这个计算的公式就叫状态转移方程，而这个性质就叫做子问题重复性。
无后效性：以及求解的子问题不受后续阶段转移和求解的影响。
最优子结构性：下一阶段的解可以由之前已经解出来的各阶段的信息推导得到。
以上三个性质，是判断一个问题能否用(DP)解决的三个基本条件。
(DP)是一种优美的算法，是(OI)中的艺术，它重点在于考察状态设计和子结构发掘能力，这是一件需要智力而非套路的事情。这也是为什么很多选手到了高二，(DP)的水平依然很低（比如我），因为他们都没有意识到这一点。