研究生课程 算法分析-动态规划

动态规划的思想

上一篇博文讲了分治法，这一篇的动态规划思想有些接近，但是两者最大区别是，动态规划要解决的子问题往往不是独立的，子问题往往被重复求解了很多次。所以一个叫朴素的想法是，把每个子问题的答案都保存下来，从而避免大量的重复计算。这种方法是典型的以空间换取时间。上一篇博文讲了分治法，这一篇的动态规划思想有些接近，但是两者最大区别是，动