分而治之和动态规划有什么区别

分而治之和动态规划是解决问题的两种算法或方法。分治算法将问题划分为子问题，并组合这些解决方案以找到原始问题的解决方案。然而，动态规划并不能独立解决子问题。它存储子问题的答案，以便将它们用于类似的问题。

分而治之，动态规划

什么是分而治之

分而治之，将主要问题分解为小的子问题。子问题被一次又一次地划分。在某一时刻，将有一个阶段，我们无法进一步划分子问题。然后，我们可以独立解决每个子问题。最后，我们可以将所有子问题的解组合起来，得到主问题的解。

分而治之有三个主要步骤。它们如下。

划分（中断） – 涉及将主要问题拆分为一系列子问题

征服（解决） – 涉及分别解决每个子问题

合并（合并） – 加入子问题的解以获得主问题的解

什么是动态规划

动态规划将主问题划分为更小的子问题，但它并没有独立解决子问题。它存储解决类似子问题时要使用的子问题的结果。存储子问题的结果称为记忆。在解决当前子问题之前，它会检查先前子问题的结果。最后，它检查所有子问题的结果以找到最佳解决方案或最优解决方案。这种方法是有效的，因为它不会一次又一次地计算答案。通常，动态规划用于优化。

动态规划的要素如下。

简单的子问题 – 将原始问题划分为具有相似结构的小子问题

问题的最优子结构 – 主问题的最优解在其子问题的最优解之内

重叠子问题 – 一次又一次地解决相同子问题的情况

分而治之和动态规划的区别

定义

分而治之是一种算法，它递归地将问题分解为两个或多个相同或相关类型的子问题，直到它变得足够简单可以直接解决。然而，动态规划是一种有助于有效解决具有重叠子问题和最优子结构属性的一类问题的算法。

类型

分而治之和动态规划之间的主要区别在于，分而治之是递归的，而动态规划是非递归的。

子问题

在分而治之中，子问题是相互独立的。然而，在动态规划中，子问题是相互依赖的。因此，这是分而治之和动态规划之间的另一个主要区别。

时间消耗

时间消耗是分治法和动态规划之间的另一个区别。分治法独立解决每个子问题。因此，它更耗时。另一方面，动态规划使用先前子问题的答案。因此，它耗时较少。

效率

效率也使分而治之和动态规划之间存在差异。动态规划比分而治之更有效。

应用

归并排序、快速排序和二分查找使用分治法，而矩阵链乘法和最优二分查找树使用动态规划。

结论

分治法与动态规划的主要区别在于，分治法是将子问题的解结合起来得到主问题的解，而动态规划则是利用子问题的结果来寻找主问题的最优解。

参考：

1. “DAA 分而治之介绍——Javatpoint。” Www.javatpoint.com，可在此处获得。2。 “动态编程介绍——Javatpoint。” Www.javatpoint.com，可在此处.3。动态规划 |设计和应用步骤 |，教育 4u，2018 年 4 月 2 日，可在此处获得。4。 “动态编程”，Programiz。 com，在这里可用。

图片提供：

1. VineetKumar 在英文维基百科的“合并排序算法图” – Eric Bauman 使用 CommonsHelper（公共领域）通过 Commons Wikimedia2 从 en.wikipedia 转移到 Commons。 “斐波那契动态编程”作者：en:User:Dcoatzee，由 User:Stannered 追踪 – en:Image:Fibonacci dynamic programming.png（公共领域）通过 Commons Wikimedia