算法与设计动态规划法.ppt

算法设计与分析 ;本 章 目 录;3.1 概 述 ;动态规划法与分治法类似其基本思想也是将待求解的问题分解成若干个子问题先求解子问题然后从这些子问题的解得到原问题的解; 与分治法不同的是适合用动态规划求解的问题经分解得到的子问题往往不是互相独立的若用分治法解这类问题则分解得到的子问题太多以致于最后解决原问题需要耗费指数时间在用分治求解时有些子问题被重复计算了多次如果能够保存已解决的子问题的答案在需