DP的基本步骤

(1)划分阶段：

按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段一定要是有序或者是可排序的（即无后效性），否则问题就无法用动态规划求解。

(2)选择状态：

将问题发展到各个阶段时包含的各种情况用不同的状态表示出来。

(3)确定决策并写出状态转移方程：

之所以把这两步放在一起，是因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以，如果我们确定了决策，状态转移方程也就写出来了。

动态规划的关键在于：按照从小到大的次序划分阶段，每个状态只需计算一次并保存下来，这样就避免了对子问题的重复计算。

动态规划的适用条件

(1)最优子结构

问题的整体最优解中包含着它的子问题的最优解，我们把这个特征叫做最优子结构，这也是动态规划求解的前提条件。如上例中“要求黑熊跳到第i个石墩时的最优解，必需先求出跳到第i-1，i-2个石墩的最优解”。

(2)无后效性

当前阶段的状态值，只与之前阶段的状态有关，不受之后阶段的影响。