退
动态规划法和分治法的区别
问题描述
动态规划法和分治法的区别，麻烦给回复
- 精选答案
-
两者的区别是：动态规划法：是把一个复杂的问题分成若干个子问题，动态规划的问题分解后的子问题通常是不互相独立的。
若还用分治的话，会因为子问题太多以至于最后解决问题需要耗费指数级的时间。分治法：将整个问题分解成若干小问题后再分而治之。如果分解得到的子问题相对来说还是太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生方便求解的子问题，必要时逐步合并这些子问题的解，从而得到问题的解。
- 其他回答
-
2. 分治法与动态规划实现方法：
① 分治法通常利用递归求解.② 动态规划通常利用迭代法自底向上求解,但也能用具有记忆功能的递归法自顶向下求解.
3. 分治法与动态规划主要区别：
① 分治法将分解后的子问题看成相互独立的.② 动态规划将分解后的子问题理解为相互间有联系,有重叠部分.
本文标题：动态规划法和分治法的区别
本文链接：https://www.bjdnbx.com/know/424807.html
转载请注明出处：来源于广知网，谢谢配合！
最新发布
