分治法与动态规划的区别 _分治法与动态规划

分治法	动态规划
1.它在递归的每个级别上处理（涉及）三个步骤：将问题分为多个子问题。通过递归解决子问题来解决它们。将子问题的解决方案合并到原始子问题的解决方案中。	1.它包括四个步骤：确定最佳解决方案的结构。递归定义最佳解决方案的值。以自下而上的最小值计算最佳解的值。根据计算的信息构造最佳解决方案。
2.它是递归的。	2.它是非递归的。
3.它在子问题上做更多的工作, 因此有更多的时间消耗。	3.它只解决一次子问题, 然后存储在表中。
4.这是一种自上而下的方法。	4.这是一种自下而上的方法。
5.在此子问题彼此独立。	5.在此子问题是相互依存的。
6.例如：合并排序和二进制搜索等。	6.例如：矩阵乘法。

分治法与动态规划的区别