算法分析大作业

2.5最终结果 3.总结 动态规划（Dynamic Programming， DP）思想启发于分治算法的思想，也是将复杂问题化解若干子问题，先求解小问题，再根据小问题的解得到原问题的解。但是DP与分治算法不同的是，DP分解的若干子问题，往往是互相不独立的，这时如果用分治算法求解，那么会对重叠子问题重复进行求解，从而使得浪费大量的时间。那么如果我们保存已经计算过的子问题的解，这样当再次计算该子问题时，可以直接使用，这样可以节约大量的时间。 设计动态规划的四个步骤： 1、刻画一个最优解的结构特征。 2、递归地定义最优解的值。 3、计算最优解的值，通常采用自底向上的方法。 4、利用计算出的信息构造一个最优解。