dp进阶之路(一)——概念与方法

前言——一点说明

本系列底稿为本人所写的同名pdf，本次更新措辞上会有一些修改，为了方便大家提交代码，题目也会进行一些更换，但基本思路不变。
在阅读过程当中遇到任何问题欢迎大家留言，发现bug也非常欢迎指正！

基本思想

动态规划是多阶段决策问题求最优解的算法（有时也计数求和），其核心是将一个问题分解为若干步的若干子问题，每一阶段都进行最优决策，来得出一个最优解。（看起来非常像贪心——事实上他就是分步的贪心）。
在我看来，dp的核心原理是分类加法原理和分步乘法原理，通过这两个原理，在当状态的上一个或几个状态中找出最优解求得当前状态，而对于前一个或者几个状态有采用同样的方法直到到达可以直接求出的边界状态。

适用条件

具有相同子问题：首先，我们必须要保证这个问题能够分解出几个子问题，并且能够通过这些子问题来解决这个问题。（这也是搜索的条件，在这一点上dp和搜索是一样的。）
满足最优化原理（最优子结构）:一个最优决策的子决策也是最优的，即一个问题的最优解一定是能从她子问题的最优解推过来的，而不是其他解。
具有无后效性：这是动态规划中极为重要的一点（也是极有可能被考察的一点），它要求每一个问题的决策，不能够对解决其它未来的问题产生影响（只有状态能产生影响，怎么到这个状态的并不重要），如果产生影响，就无法保证决策的最优性，这就是无后效性。
这些往往这需要我们找到一个合适状态，即当你发现当前状态不满足以上三点的时候很有可能是你状态选择错误。

个人最常用的解题步骤

确定原问题的子问题——要点：注意分析哪些量随着问题规模的变小是会变小的（即求解原问题的时候需要知道什么），哪些变量与问题无关。
确定状态——要点：结合子问题，敢想敢试（高维也不要怕），不要轻易否定一个状态，多思考，不要希望每个题都能一蹴而就，状态不合适也要想清楚哪里不合适，然后也许你就能修正了！
推出状态转移方程 ——要点：枚举最后一次决策，注意验证适用条件是否满足，注意不要漏掉条件。
确定边界条件——要点：先根据状态含义确定，确定后验证第一层是否正确，如果不正确或者无法按含义确定，则也可以采用第一层的值反推的方式确定边界。
确定实现方式——要点：根据拓扑序是否明显和个人习惯确定！
如果需要的话，确定优化方法！——要点：注意优先考虑能否降维，不要局限于单调队列，四边形不等式这些标准的用于dp优化的东西，扩宽思维，避免定式！

《动态规划经典》中提到的几种解题方法

模型匹配法：很多同学最常使用的就是这个方法，如果发现问题是自己熟悉的某个基本的模型，就直接套用，但要小心其中的一些小的变动（本方法适用于经典模型的变形题，但是总是这样想会导致思维定式和经验主义，并且在遇到一个没有见到的题目时可能会影响分析了）
三要素法：仔细分析问题尝试着确定动态规划的三要素，不同问题的却定方向不同——先确定阶段的问题：数塔问题；先确定状态的问题：大多数都先确定状态的；先确定决策的问题：背包问题。
寻找规律法：这个方法很简单，耐心推几组数据后，看他们的规律，总结规律间的共性，有。
边界条件法：找到问题的边界条件，然后考虑边界条件与它的领接状态之间的关系。
放宽约束和增加约束：给问题增加一些条件或删除一些条件使问题变的清晰，甚至变成你熟悉的问题，然后再考虑变回去。（其实很多类型的题都可以这样考虑，由浅入深，由简到难）。