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