algorithm - 动态规划与分而治之的区别

Question

分而治之和动态规划之间的主要区别是什么？如果我们举个例子，归并排序基本上是通过使用递归的分而治之来解决的。动态编程也基于递归而不是合并排序为什么不被认为是动态编程的一个例子？

Answer 1

两者的相似之处在于它们都将问题分解为小问题并解决了这些问题。然而，在分治法中，子问题是独立的，而在动态规划中，子问题是相互依赖的。两者都需要以某种方式重新组合子问题，但区别在于子问题是否与（相同“级别”的）其他子问题相关

D&C 示例：合并排序

在 Mergesort 中，您将排序分解为许多小的“子排序”，也就是说，不是排序 100 个项目，而是排序 50，然后是 25，等等。但是，在将原始项目分解为（例如）4 个“子排序”之后sorts”，不管你先做什么；顺序无关紧要，因为它们是独立的。重要的是他们最终会完成。因此，每次，您都会得到一个完全独立的问题，并有自己的正确答案。

DP 示例：递归斐波那契

尽管存在子问题，但每个问题都直接构建在另一个之上。如果你想要第 10 位，你必须以特定的顺序解决问题（1+2、2+3 等）。因此，它们不是独立的。

Answer 2

当子问题独立时使用 D&C。当递归函数重复相同的递归调用时需要动态编程。

以斐波那契递归为例：f(n)=f(n-1)+f(n-2)

例如：

f(8) = f(7) + f(6) = ( f(6) + f(5) ) + f(6)

如您所见，f(6) 将被计算两次。从递推关系来看，显然重复值太多了。最好记住这些值，而不是一遍又一遍地计算。dp 中最重要的是记住这些计算值。如果您查看 dp 问题，通常使用数组或矩阵来防止重复计算。

与 dp 相比，d&c 通常将问题划分为独立的子问题，无需记住任何值。

Answer 3

所以我会说D&C是一个更大的概念，而DP是一种特殊的D&C。具体来说，当你发现你的子问题需要共享相同较小子问题的一些计算时，你可能不希望它们一次又一次地计算相同的东西，你缓存中间结果以加快时间，这就是 DP。所以，本质上，我认为 DP 是 D&C 的快速版本。