（Note）动态规划的基本步骤

动态规划算法依赖于以下两个性质：

1. 最优子结构：问题的最优解是由最优子问题的最优解推出的，也就是问题的最优解包含了子问题的最优解。
2. 重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不是总是新问题。有些子问题被反复计算多次。

动态规划算法对每一个子问题只解一次，而后将其保存在一个表格中，在之后利用这些子问题的解。

动态规划的基本步骤是：

（1）找出最优解的性质，并且刻画其结构特征

（2）递归地定义最优值

（3）以自底向上的方式，将问题分解为各个小问题，一步步地计算出最优值

（4）根据计算最优值时得到的信息，构造一个最优解。