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

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

覆盖的关键领域

1.什么是分而治之-定义，功能2.什么是动态规划-定义，功能3.分而治之和动态规划的区别是什么-关键区别的比较

关键术语

分而治之，动态规划

什么是分而治之(divide and conquer)？

分而治之把主要问题分解成小的子问题。子问题被一次又一次地划分。在某一点上，会有一个阶段，我们不能进一步划分子问题。然后，我们可以独立地解决每个子问题。最后，我们可以将所有子问题的解结合起来，得到主问题的解。

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

分解（Break）–将主要问题分解为一系列子问题

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

合并（Merge）–合并子问题的解决方案以获得主问题的解决方案

什么是动态规划(dynamic programming)？

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

动态规划的要素如下。

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

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

重叠子问题–反复解决同一个子问题的情况

分(divide)和征服(conquer)的区别

定义

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

类型

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

子问题

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

时间消耗

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

效率

效率也是分而治之和动态规划的区别。动态规划比分而治之更有效。

应用

合并排序、快速排序和二进制搜索使用分治，而矩阵链乘法和最优二叉搜索树采用动态规划。

结论

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

引用

1.“DAA分而治之简介–Javatpoint.”Www.Javatpoint.com，可在此处获得。2动态编程简介-Javatpoint。“Www.Javatpoint.com，可在此处获得。3。动态规划设计步骤；申请|，教育4u，2018年4月2日，可在此处获取。4。“动态规划“， 编程。com，这里提供。 2.“动态规划简介–Javatpoint”，Www.Javatpoint.com， 3.动态规划|设计与应用步骤|，教育4u，2018年4月2日， 4.“动态规划”， 编程。通用域名格式，