共同点： 将待求解的问题分解成若干子问题，先求解子问题，然后再从这些子问题的解得到原问题的解。不同点：1、适合于用动态规划法求解的问题，分解得到的各子问题往往不是相互独立的； 而分治法中子问题相互独立。2、动态规划法用表保存已求解过的子问题的解，再次碰到同样的子问题时不必重新求解，而只需查询答案，故可获得多项式级时间复杂度，效率较高； 而分治法中对于每次出现的子问题均求解，导致同样的子问题被反复求解，故产生指数增长的时间复杂度，效率较低。
1、分治法
2、动态规划
原理参见 屈婉玲老师 算法设计与分析 ORZ
1. 分治法与动态规划主要共同点:二者都要求原问题具有最优子结构性质,都是将原问题分而治之,分解成若干个规模较小(小到很容易解决的程序)的子问题.然后将子问题的解合并,形成原问题的解. 2. 分治法与动态规划实现方法:① 分治法通常利用递归求解.② 动态规划通常利用迭代法自底向上求解,但也能用具有记忆功能的递归法自顶向下求解. 3. 分治法与动态规划主要区别:① 分治法将分解后的子问题看成相互独立的.② 动态规划将分解后的子问题理解为相互间有联系,有重叠部分.
1、对问题进行分解的算法策略——分治法与动态规划法共同点：（1）分治法与动态规划法实际上都是递归思想的运用（2）二者的根本策略都是对问题进行分解，找到大规模与小规模的关系，然后通过解小规模的解，得出大规模的解不同点： 适用于分治法的问题分解成子问题后，各子问题间无公共子子问题，而动态规划法相反。动态规划法 = 分治算法思想 + 解决子问题间的冗余情况2、多阶段逐步解决问题的策略——贪心算法和动态规划法贪心算法：每一步都根据策略得到一个结果，并传递到下一步，自顶向下，一步一步地做出贪心决策。动态规划算法：每一步决策得到的不是一个唯一结果，而是一组中间结果（且这些结果在以后各步可能得到多次引用），只是每一步都使问题的规模逐步缩小，最终得到问题的一个结果。
218 浏览 4 回答
105 浏览 3 回答
203 浏览 4 回答
296 浏览 2 回答
163 浏览 2 回答
172 浏览 2 回答
306 浏览 5 回答
192 浏览 2 回答
163 浏览 4 回答
302 浏览 4 回答
188 浏览 5 回答
328 浏览 6 回答
272 浏览 2 回答
329 浏览 6 回答
204 浏览 4 回答
235 浏览 2 回答
112 浏览 4 回答
186 浏览 2 回答
224 浏览 2 回答
149 浏览 4 回答
265 浏览 4 回答
151 浏览 2 回答
178 浏览 2 回答
320 浏览 2 回答
89 浏览 4 回答
哈毛小子
