分治法与动态规划的区别

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

    推荐阅读