思路

动态规划的核心即为拆分子问题，记住过往，减少重复计算。并且动态规划一般都是自底向上的，所以动态规划思路一般为：

1. 穷举分析
2. 确认边界
3. 找出规律，确认最优子结构
4. 写出状态转移方程

条件

无后效性

无后效性是指如果在某个阶段上过程的状态已知，则从此阶段以后过程的发展变化仅与此阶段的状态有关，而与过程在此阶段以前的阶段所经历过的状态无关。 利用动态规划方法求解多阶段决策过程问题，过程的状态必须具备无后效性。

最优子结构性质

子问题的局部最优将导致整个问题的全局最优。