动态规划算法（DP,Dynamic Programming）

它针对满足特定条件的一类问题，对各状态维度进行分阶段、有顺序、无重复、决策性的遍历求解。

阶段

动态规划算法把原问题视作若干个重叠子问题的逐层递进，每个子问题的求解过程都构成一个阶段。在完成前一个阶段的计算后，动态规划才会执行下一阶段的计算。

状态

一般用于描述问题的客观条件。

无后效性

为了保证这些计算能够按顺序、不重复地进行，动态规划要求已经求解的子问题不受后续阶段的影响。

最优子结构

很多情况下，动态规划用于求解最优化问题。此时下一阶段的最优解应该能够由前面各阶段子问题的最优解导出。其实更一般的说法是，动态规划在阶段计算完成时，只会在每个状态上保留与最终解集相关的部分代表信息，这些代表信息应该具有可重复求解的过程，并能够导出后续阶段的代表信息。这样的话，动态规划对状态的抽象和子问题的重叠递进才能够起到优化作用。

状态转移方程

动态规划算法把相同的计算过程用于各阶段的同类子问题，就好像把一个固定的公式在格式相同的若干个输入数据上运行。而这个 “公式” 就是状态转移方程。这里也一般是动态规划最核心的部分了，决定了你最后能否正确导出你想要的那个状态的答案。