What is DP?
学习的开始，我们需要一个具体的学习对象，什么是 (DP)？
(DP)，即 动态规划((Dynamic Programming))，是运筹学的一个分支，是求解 决策过程最优化 的数学方法。
在使用 (DP) 求解的题目中，问题往往可以被分为几个“阶段”，通过对之前求解的与当前状态有联系的状态结果对当前状态进行更新和计算。
(DP) 的特点
- 无后效性
动态规划问题的求解要求已经求过解的状态不会受到之后任何状态变化的影响而发生改变
当前的状态已经是对过去发生的一系列决策的一个完整总结，已经求解过的历史状态只能通过当前状态的解来间接影响未来过程的演变。
【动态规划，就像是我们身边流过的时间，离去的已成过往，不会因现在而改变，但我们此刻的所作所为，却能够决定各自的未来。】
- 最优化原理
对于动态规划的整个过程，不论当前状态的决策如何，历史决策所形成的状态都是其在规则内的最优解。动态规划最后所达到的最优结果，可以看作是由历史的所有状态的最优解达到的状态，整体的最优状态也可以分解成局部的各个状态的最优决策。
在这一点上和贪心有一点相似，但是要注意贪心是每次只取当前的最大价值，而动态规划则要根据当前和历史状态进行选择。（目光短浅和轻车熟路）
- 动态规划的三要素
即 “状态”、“阶段”、“决策”。
在同台规划问题中，我们通常通过对状态的定义和分析将问题分为数个阶段，并在不同的阶段中进行不同的决策，以达到答案所在的状态，获得正解。
What are the features of problems?
作为一种常见的算法，(DP) 的作用肯定是帮助我们求解特定问题，我们应如何判断一个问题是否适用于 (DP) 呢？
动态规划的题目通常会带有有以下的特点：
-
需要求解问题的最值或满足条件的极限状态
-
最终问题可以被分为若干个子问题
-
满足“无后效性”原理，即后来的决策不会影响已经被确定过的状态
有时，题目中带有动态规划特征的信息并不明显或有所不同，例如这道题：洛谷 P5020 货币系统
本题一看之下可能会认为是一道计数类的题目，并不会和 (DP) 联系起来。但是我们分析题目后可以发现，这道题其实和可行性有关，而我们可以将 (DP) 中的“状态”直接表示为其是否可行。即如果我们在动态规划中经过了这个状态，则说明这个状态是可行的。而在这道题目中，对于一个固定的金额，它是否能够被表示可以变为它的若干个部分是否能够被表示，而它自身能够被表示并不会使得在它之前的金额的可行性有所变化，满足动态规划的要求，因此，我们就可以考虑使用动态规划来求解这道题目。
当然，我们有时并不一定一眼就能看出题目中隐含的上述特点，这就需要日常练习和刷题来提高自己分析题目的能力了。
How to solve the problem?
现在，我们有了问题，那么，我们应如何使用这个算法呢？
一般的动态规划问题可以分为以下三个步骤：
- 通过题目的描述和要求确定动态规划的“状态”
在确定状态时大多动态规划题目中不会很明显地给出合适的状态，需要我们自己进行定义（一般是使用多维数组进行定义，数组的一位代表了对应状态中的一个变量）。需要注意的是使用数组对状态进行定义时，维数的增加往往意味着空间和时间复杂度的增加，要注意 TLE 和 MLE 带来的错误。
确定状态时，有一个常用的技巧：如果当前的状态较难准确定义，我们可以先进行“加维”，定义成功后通过状态转移方程把不必要的或者能够通过滚动数组优化掉（滚掉）的维度删除即可。
- 根据定义的状态推出状态转移方程
状态转移方程是用于处理若干格式相同的状态的固定公式，可以包含多个不同的式子，但是必须包含除问题边界之外的所有可能达到的状态，以此来达到“状态转移”的效果。
状态转移方程是动态规划问题的灵魂关键部分，它决定了一篇代码的正确与否。同时，能否正确且迅速地找出题目的状态转移方程，也是对一名 (OIer) 在竞赛知识和思维深度等方面的综合考验。
当我们已经做过多道动态规划的题目时，我们对状态转移方程的推导有时会和定义状态同时进行。在我们尝试不同的状态定义方式时，也可以同时考虑其作为状态转移方程中的一个变量的可行性，在定义状态的同时加上对此状态下的状态转移方程的思考会对推导的过程有很大的帮助。
- 确定当前问题的边界条件
正如列车有自己的起始和轨道矩阵有其大小，搜索也会越界，动态规划问题也有自己的边界。通常情况下这些边界为当状态为一些特殊值（如 1 或 0 等特殊数字）或者限制条件的极限状态。状态转移方程在这些状态上并不适用或是需要用到这些状态的特殊性和对应值进行状态转移。
当我们已经确定状态和状转方程之后，边界通常会很明显地显现在我们眼前，当然，不排除一些微小而又难以发现的特殊情况。这就需要看各位 (OIer) 的认真和细心啦~（许多 (dalao) 们的较量有时也会体现在这一点上）
The Last
动态规划是 (OI) 中重要的一个知识点，在考试中也会和很多其他算法进行搭配考察，是一个十分重要的算法思想。
对于动态规划的学习并没有什么捷径可走，我的建议是多刷题，多练习，只有自己将动态规划融入自己的知识框架并能够熟练运用，才能够在 (DP) 这一片天地中自由驰骋。
当然，(DP) 也有很多不同的种类和优化，如树上 (DP)、单调队列优化、斜率优化……，在这里我只说最基础的框架，其他的我有时间了说不定也会总结一下~
那么，对动态规划的学习笔记就先写到这里吧~
完结撒fa~