算法策略间的关系

0 人点赞了该文章 · 33 浏览

算法策略间的关系

　　1、对问题进行分解的算法策略——分治法与动态规划法

　　共同点：（1）分治法与动态规划法实际上都是递归思想的运用

　　　　　　（2）二者的根本策略都是对问题进行分解，找到大规模与小规模的关系，然后通过解小规模的解，得出大规模的解

　　不同点：适用于分治法的问题分解成子问题后，各子问题间无公共子子问题，而动态规划法相反。

　　动态规划法 = 分治算法思想 + 解决子问题间的冗余情况

　　2、多阶段逐步解决问题的策略——贪心算法和动态规划法

　　贪心算法：每一步都根据策略得到一个结果，并传递到下一步，自顶向下，一步一步地做出贪心决策。

　　动态规划算法：每一步决策得到的不是一个唯一结果，而是一组中间结果（且这些结果在以后各步可能得到多次引用），只是每一步都使问题的规模逐步缩小，最终得到问题的一个结果。　