分治算法与动态规划的区别

分而治之

分而治之的工作方式是将问题划分为子问题，递归地征服每个子问题并将这些解决方案组合起来。

动态规划

动态规划是一种解决具有重叠子问题的问题的技术。每个子问题只解决一次，每个子问题的结果存储在一个表中（通常实现为数组或哈希表）以供将来参考。这些子解决方案可用于获得原始解决方案，并且存储子问题解决方案的技术称为记忆。

您可能会想到DP = recursion + re-use

理解差异的经典示例是查看这两种方法来获得第 n 个斐波那契数。从 MIT 检查这个 material。

https://i.stack.imgur.com/QBJIj.png

https://i.stack.imgur.com/rFqdb.png

---

动态规划和分而治之的相似性

正如我现在所看到的，我可以说动态编程是分而治之范式的扩展。

我不会将它们视为完全不同的东西。因为它们都通过递归地将问题分解为相同或相关类型的两个或多个子问题来工作，直到这些子问题变得足够简单可以直接解决。然后将子问题的解决方案组合起来以给出原始问题的解决方案。

那么为什么我们仍然有不同的范例名称以及为什么我将动态编程称为扩展。这是因为只有当问题具有某些限制或先决条件时，才可以将动态规划方法应用于问题。之后，动态规划通过记忆或制表技术扩展了分而治之的方法。

让我们一步一步来……

动态规划先决条件/限制

正如我们刚刚发现的那样，为了使动态规划适用，分而治之问题必须具有两个关键属性：

最优子结构——最优解可以从其子问题的最优解构造

重叠的子问题——问题可以分解成多次重复使用的子问题，或者问题的递归算法一遍又一遍地解决相同的子问题，而不是总是产生新的子问题

一旦满足这两个条件，我们可以说这个分而治之的问题可以使用动态规划方法来解决。

分而治之的动态规划扩展

动态编程方法通过两种技术（memoization 和 tabulation）扩展了分而治之的方法，这两种技术都旨在存储和重用可以显着提高性能的子问题解决方案.例如，斐波那契函数的朴素递归实现具有 O(2^n) 的时间复杂度，其中 DP 解决方案仅用 O(n) 时间做同样的事情。

记忆化（自上而下的缓存填充）是指缓存和重用先前计算结果的技术。因此，memoized fib 函数如下所示：

memFib(n) {
    if (mem[n] is undefined)
        if (n < 2) result = n
        else result = memFib(n-2) + memFib(n-1)
        
        mem[n] = result
    return mem[n]
}

制表（自下而上的缓存填充） 类似，但侧重于填充缓存的条目。计算缓存中的值最容易迭代完成。 fib 的表格版本如下所示：

tabFib(n) {
    mem[0] = 0
    mem[1] = 1
    for i = 2...n
        mem[i] = mem[i-2] + mem[i-1]
    return mem[n]
}

您可以阅读有关记忆和制表比较的更多信息here。

您应该在这里掌握的主要思想是，由于我们的分而治之问题具有重叠的子问题，子问题解决方案的缓存成为可能，因此记忆/制表步入了现场。

那么DP和DC到底有什么区别

由于我们现在熟悉 DP 先决条件及其方法，我们准备将上面提到的所有内容放在一张图片中。

https://cdn-images-1.medium.com/max/2000/1*BwuDAdImyK_nZpb-H8h3SA.jpeg

如果您想查看代码示例，可以查看 more detailed explanation here，其中有两个算法示例：二分搜索和最小编辑距离（Levenshtein 距离），它们说明了 DP 和 DC 之间的区别。

---

分而治之和动态规划之间的另一个区别可能是：

分而治之：

在子问题上做更多的工作，因此需要更多的时间。在分而治之中，子问题是相互独立的。

动态规划：

仅解决子问题一次，然后将其存储在表中。在动态规划中，子问题不是独立的。

---

有时在递归编程时，您多次调用具有相同参数的函数，这是不必要的。

著名的斐波那契数列示例：

           index: 1,2,3,4,5,6...
Fibonacci number: 1,1,2,3,5,8...

function F(n) {
    if (n < 3)
        return 1
    else
        return F(n-1) + F(n-2)
}

让我们运行 F(5)：

F(5) = F(4) + F(3)
     = {F(3)+F(2)} + {F(2)+F(1)}
     = {[F(2)+F(1)]+1} + {1+1}
     = 1+1+1+1+1

所以我们称： 1 次 F(4) 2 次 F(3) 3 次 F(2) 2 次 F(1)

动态编程方法：如果多次调用具有相同参数的函数，则将结果保存到变量中，以便下次直接访问。迭代方式：

if (n==1 || n==2)
    return 1
else
    f1=1, f2=1
    for i=3 to n
         f = f1 + f2
         f1 = f2
         f2 = f

让我们再次调用 F(5)：

fibo1 = 1
fibo2 = 1 
fibo3 = (fibo1 + fibo2) = 1 + 1 = 2
fibo4 = (fibo2 + fibo3) = 1 + 2 = 3
fibo5 = (fibo3 + fibo4) = 2 + 3 = 5

如您所见，每当您需要多次调用时，您只需访问相应的变量即可获取值，而不是重新计算它。

顺便说一句，动态编程并不意味着将递归代码转换为迭代代码。如果需要递归代码，还可以将子结果保存到变量中。在这种情况下，该技术称为记忆化。对于我们的示例，它看起来像这样：

// declare and initialize a dictionary
var dict = new Dictionary<int,int>();
for i=1 to n
    dict[i] = -1

function F(n) {
    if (n < 3)
        return 1
    else
    {
        if (dict[n] == -1)
            dict[n] = F(n-1) + F(n-2)

        return dict[n]                
    }
}

所以与分治的关系是 D&D 算法依赖于递归。它们的某些版本具有这种“具有相同参数问题的多个函数调用”。搜索“矩阵链乘法”和“最长公共子序列”以获得需要 DP 来改进 D&D 算法的 T(n) 的示例。

---

我假设您已经阅读过 Wikipedia 和其他学术资源，所以我不会回收任何这些信息。我还必须警告说，我无论如何都不是计算机科学专家，但我会分享我对这些主题的理解的两分钱......

动态规划

将问题分解为离散的子问题。斐波那契数列的递归算法是动态规划的一个例子，因为它通过首先求解 fib(n-1) 来求解 fib(n)。为了解决原来的问题，它解决了一个不同的问题。

分而治之

这些算法通常会解决问题的相似部分，然后在最后将它们放在一起。合并排序是分而治之的经典例子。这个例子和斐波那契例子的主要区别在于，在归并排序中，分割（理论上）可以是任意的，而且无论你如何分割它，你仍然在归并和排序。无论您如何划分数组，都必须完成相同数量的工作来对数组进行归并排序。求解 fib(52) 比求解 fib(2) 需要更多的步骤。

---

我认为 Divide & Conquer 是一种递归方法，而 Dynamic Programming 是表格填充。

例如，Merge Sort 是一个 Divide & Conquer 算法，因为在每一步中，您将数组分成两半，在两半上递归调用 Merge Sort，然后合并它们。

Knapsack 是一种 Dynamic Programming 算法，因为您正在填写一个代表整个背包子问题的最佳解决方案的表格。表中的每个条目对应于在给定项目 1-j 的情况下，您可以在一袋重量 w 中携带的最大值。

---

分而治之在每个递归级别涉及三个步骤：

将问题分解为子问题。通过递归解决子问题来征服子问题。将子问题的解决方案合并到原始问题的解决方案中。这是一种自上而下的方法。它在子问题上做了更多的工作，因此花费了更多的时间。例如。斐波那契数列的第 n 项可以以 O(2^n) 时间复杂度计算。

动态规划包括以下四个步骤： 1. 表征最优解的结构。 2.递归定义最优解的值。 3. 计算最优解的值。 4. 从计算的信息构造一个最优解。

这是一种自下而上的方法。

由于我们使用之前计算的值，而不是再次计算，因此比分治法消耗更少的时间。

例如。斐波那契数列的第 n 项可以以 O(n) 时间复杂度计算。

为了更容易理解，让我们将分而治之视为一种蛮力解决方案，并将其优化视为动态规划。 NB 具有重叠子问题的分治算法只能使用 dp 进行优化。

---

分而治之 他们闯入了不重叠的子问题 示例：阶乘数 ie fact(n) = n*fact(n-1)

他们闯入了不重叠的子问题

示例：阶乘数，即 fact(n) = n*fact(n-1)

fact(5) = 5* fact(4) = 5 * (4 * fact(3))= 5 * 4 * (3 *fact(2))= 5 * 4 * 3 * 2 * (fact(1))

正如我们在上面看到的，没有事实（x）被重复，所以阶乘没有重叠问题。

动态规划他们分解成重叠的子问题示例：斐波那契数即 fib(n) = fib(n-1) + fib(n-2)

他们分解成重叠的子问题

示例：斐波那契数，即 fib(n) = fib(n-1) + fib(n-2)

fib(5) = fib(4) + fib(3) = (fib(3)+fib(2)) + (fib(2)+fib(1))

正如我们在上面看到的，fib(4) 和 fib(3) 都使用 fib(2)。同样，如此多的 fib(x) 被重复。这就是斐波那契有重叠子问题的原因。

由于 DP 中子问题的重复，我们可以将这些结果保存在一个表中，从而节省计算量。这被称为记忆

---

分而治之

在这个问题中解决以下三个步骤： 1. Divide - 划分为子问题的数量 2. Conquer - 通过递归解决子问题来征服 3. Combine - 组合子问题的解决方案以获得原始问题的解决方案

递归方法

自上而下技术

示例：合并排序

动态规划

在此问题通过以下步骤解决： 1. 定义最优解的结构 2. 反复定义最优解的值。 3. 以自下而上的方式获得最优解的值 4. 从获得的值中得到最终的最优解

非递归

自下而上技术

示例：Strassen 的矩阵乘法

---