动机

动态规划一直是赛事常客，其变种更是花样百出。

Besides，动态规划的推导易错，容易出现有思路却不能拿分的情况。

我之前做过很多与DP相关的分享，本篇或许是整理补充。

理解

动态规划，是一种分层次解决问题的算法。或许不清晰？

换句话说，动态规划分为divide，compare，transfer，integration(pull together)几部分

DP其实只是属于一种mathematics，in fact，不用太过神话。

就像未知元重在代指未知量以达到表示具体情景进而方便联系求解的作用，

DP也是通过代指未知量，进而分析便于联系转移。

简言之，是目标、对象类的一种mathematics

实现

根据y总的方法，可以用集合的方式分化DP，从属性出发，设立集合的表示，进而divide,transfer解决

这里是彩铅的图示：

对于转移困难的问题我们有状态机，就是将状态变为结点，边变为转移。

这样可以让一部分的转移机更加清楚，却不意味着减少了复杂度。

但状态机太多也要用分类讨论的方式。

不过还有很多有些反常的DP

比如说数据结构优化DP,矩阵优化DP,高斯消元DP,状压插头DP,数位DP,单调优化DP和斜率优化DP。

他们大部分都和之前的DP设计有很大区别了。

就像是有特别多的trick混合，你可以通过复杂度和一些要求/变形看出他们是哪一类trick,

然后就要用特定的技巧进行解决。

他们大部分都是用到了DP的技巧的，但很多方法都有进一步的简化，就像数位DP，他虽然是用记忆化搜索解决的，但也是DP的转移方式，不过会用到数学的其它方法，其实编程就是这样，特定的技巧能解决的只有标准的问题，变化的问题就是要从化归的思想解决了。