动态规划（Dynamic Programming）：即是数学优化法也是计算机编程的方法（递推方法的计算机实现）。

任何数学上用递归表示问题也可以被表示为计算机的递归算法，但是许多情况下，会出现大量的重复计算而导致性能问题。所以，为了解决性能问题，我们把已知求解完成的子问题结果记录下来，然后把递归转换成非递归，根据前面的子问题结果推到出最终问题的解。而把这个方法技巧称为：动态规划。

注意：根据 Dynamic Programming 的含义，理解为递推更合适。

可以动态规划解决问题都是具有如下特征：

• 问题可分解为子问题
• 一般带有最优、最值、最佳等字样
• 问题最终解可以由一些条件，由子问题的解逐步递推求解
• 保存最优子结构（淘汰次优解）

解题关键：找重复子问题，推到最终解。

1）寻找最优子结构：

2）保存中间状态（重要，有时候需要根据条件升维，或根据问题进行优化）

3）根据子结构，构建递推公示（DP 方式，状态转移方程）推导最终解

4）编写算法实现

• 自顶向下法：从已知条件，初始值逐步推导最终问题
• 自底向上法：从最终结果开始，向前逐步推导，找到递推关系