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

Question

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

Answer 1

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

D&C 示例:Mergesort

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

DP 示例:递归斐波那契

虽然有子问题，但每个问题都直接建立在另一个问题之上。如果您想要第 10 位数字，则必须按特定顺序解决构成该数字(1+2、2+3 等)的问题。因此，它们不是独立的。