动态规划

适合求解的问题

动态规划通常用来求解最优化问题，适合求解的问题需要满足两个特点：

• 最优子结构
• 重叠子问题。

最优子结构是确定动态规划算法的正确性，通常用数学归纳法来证明问题是否具有最优子结构特点；重叠子问题是确定动态规划算法的计算效率。

设计步骤

1. 刻画一个最优解的结构特征
2. 递归地定义最优解的值
3. 计算最优解的值，通常采用自底向上的方法
4. 利用计算出的信息构造一个最优解