可能很多人都不知道怎么做DP题，一般有如下问题：

这道题是不是DP？

DP的状态该怎么设？

转移过程怎么写，怎么确定转移方程？

转移过程怎么优化？

为什么其它内容似乎没有问题，但答案不对？

DP的定义

DP是满足可以通过数组存储代表某一个状态的答案并优化了时间复杂度的算法。

这意味着DP需要满足最优子结构性和无后效性。

熟练的处理组合式子也是DP题求解的重点。

事实上，DP的核心只有状态，转移方程。

yxcDP的问题

yxc的DP方法是将DP看成了一个集合，但集合的定义不能直接用于DP中，因为集合只是描述元素是否在集合里，而不能描述元素对应的答案。

不过，解决这个问题的方法是，DP中元素对应的答案经常是固定的类型，如$Min,Max,Num$，这使得只要另一个集合中的元素都指向这一个类型，逻辑就可以解释了。

集合表述的优越性在于，它天然关注到了一个元素只出现一次。但却忽略了DP划分子问题的特征，yxc通过新增阶段概念来打补丁，但这个补丁有一个大的隐患，就是部分DP没有阶段特征，而且哪怕是有阶段特征的，用椭圆表示也会画蛇添足。

状态设计原理

通常且合理的设计方法是，关注DP状态，在由此推出转移方程。但同样这个方法也有问题，DP状态简直像凭空出现的一样，一定有一些方法合理得到状态。

而方法如下：

第一步

将所有影响元素都设为状态，确保一个状态一定对应一个答案。

影响元素类型

物品数量，费用，是否选择第i个物品，两个串匹配了k个点，在一排选择了k个元素其它排供选择n-k个元素。这些是背包DP和匹配DP。

如果合并顺序会影响答案，但只能相邻元素合并时需用区间DP。

一些需预处理的地方会用到倍增DP。

树上会用到树形DP。

状态机会继续根据不同类型的操作状态划分状态。

如果必须知道具体用了哪些物品/元素点，得用状压DP。

第二步

发掘性质，优化DP状态。

这是DP最难的一步，通常可以从以下方法考虑：

设更少的状态，排斥冗余。

结合贪心，维护更少的状态。

结合性质，从特定方式加入，用更快速的方法计算一些点。

转化题目，如容斥，差分。

变化DP主体。

拆位。

关注某个具体元素的影响。

限制值域。

分类讨论。

末状态倒推。

......

第三步

写出DP转移方程，用一些技巧加速转移。

第四步

差错。检查代码错误，检查写错的部分，检查逻辑错误（常见如算重了）

这便是解决问题的三个步骤。