第三章动态规划算法.PPT

动态规划算法将原问题分解为若干个子问题，先求子问题的解，然后从这些子问题的解得到原问题的解。这些子问题的解往往不是相互独立的。在求解的过程中，许多子问题的解被反复地使用。为了避免重复计算，动态规划算法采用了填表来保存子问题解的方法。在算法中用表格来保存已经求解的子问题的解，无论它是否会被用到。当以后遇到该子问题时即可查表取出其解，避免了重复计算。