动态规划法和分治法的区别

问题描述

精选答案

两者的区别是：

动态规划法：是把一个复杂的问题分成若干个子问题，动态规划的问题分解后的子问题通常是不互相独立的。若还用分治的话，会因为子问题太多以至于最后解决问题需要耗费指数级的时间。

分治法：将整个问题分解成若干小问题后再分而治之。如果分解得到的子问题相对来说还是太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生方便求解的子问题，必要时逐步合并这些子问题的解，从而得到问题的解。

其他回答

IT海盗

2. 分治法与动态规划实现方法：

① 分治法通常利用递归求解.② 动态规划通常利用迭代法自底向上求解,但也能用具有记忆功能的递归法自顶向下求解.3. 分治法与动态规划主要区别：

① 分治法将分解后的子问题看成相互独立的.② 动态规划将分解后的子问题理解为相互间有联系,有重叠部分.