第四章算法设计与分析-动态规划(10)

动态规划算法的基本要素：

二、子结构重叠性质

递归算法求解问题时，每次产生的子问题并不总是 新问题，有些子问题被反复计算多次。这种性质称 为子问题的重叠性质。 动态规划算法，对每一个子 问题只解一次，而后将其解保存在一个表格中，当 再次需要解此子问题时，只是简单地用常数时间查 看一下结果。 通常不同的子问题个数随问题的大小 呈多项式增长。因此用动态规划算法只需要多项式 时间，从而获得较高的解题效率。12/14/2012 6:50 PM 10