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

Question

分治算法和动态规划算法有何区别？这两个术语有何不同之处？我不理解它们之间的差异。

请用一个简单的例子解释二者之间的任何差异以及它们似乎相似的原因。

- saplingPro

Answer 1

分治算法（Divide and Conquer）

分治算法将问题划分成子问题，递归地处理每个子问题并将这些解合并起来。

动态规划（Dynamic Programming）

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

你可以将动态规划看作是“递归+重复使用”的组合。

理解两种方法之间的区别的一个经典例子是查找第n个斐波那契数。请参考麻省理工学院的资料。

---

分治算法方法

动态规划方法

- OneMoreError

---

你是如何制作这些图片的？使用鼠标吗？ - Vihaan Verma

我认为这整个答案中最重要的一句话是：“重叠子问题”。动态规划具有这一特点，而分治法则没有。 - QuestionEverything

@HasanIqbalAnik 重叠子问题指的是一个问题一次又一次地出现。就像在上面所示的例子中解决 fn-2 一样。因此，在分治算法中，这个问题是存在的，这就是为什么它不像动态规划那样高效的原因。 - Meena Chaudhary

奇怪！你说的“重叠子问题”是一个问题，但“动态规划”是一种算法。我认为区分“问题”和“算法”很重要。 - ZHU

是的，DP会记忆化重叠部分以获得比分治更好的优势。 - imagineerThat

Answer 2

动态规划与分治算法的相似之处

就目前而言，我可以说动态规划是分治范例的一种扩展。

我不认为它们是完全不同的东西。因为它们都通过递归将问题分解成两个或多个相同或相关类型的子问题，直到这些问题变得足够简单，可以直接求解。然后将子问题的解合并起来，给出原始问题的解。

那么我们为什么仍然有不同的范例名称，以及为什么我称动态规划是一种扩展呢？这是因为只有在问题具有某些限制或前提条件时，才能应用动态规划方法。之后，动态规划使用记忆化或表格法技术扩展了分治法。

让我们一步一步来...

动态规划的前提条件/限制

正如我们刚刚发现的，分治问题必须具备两个关键属性，才能使动态规划适用：

• 最优子结构 - 最优解可以由其子问题的最优解构造出

• 重叠子问题 - 问题可以被分解为多个子问题，这些子问题被多次重复使用，或者针对该问题的递归算法反复解决同一子问题，而不总是生成新的子问题。

只要满足这两个条件，我们就可以说这个分治问题可以使用动态规划方法来解决。

动态规划扩展的分治法

动态规划方法通过两种技术（记忆化和表格法）扩展了分治法，这两种技术都具有存储和重复使用子问题解决方案的目的，可以极大地提高性能。例如，斐波那契函数的朴素递归实现具有时间复杂度为O(2^n)，而相同功能的DP解决方案仅需要O(n)的时间。

记忆化（自顶向下的缓存填充）指的是缓存和重新使用先前计算的结果的技术。因此，记忆化的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的先决条件和方法，我们就可以将上面提到的所有内容整合到一张图片中。

如果您想查看代码示例，可以在这里查看更详细的说明，其中包括两个算法示例：二分查找和最小编辑距离（Levenshtein Distance），它们说明了DP和DC之间的区别。

- Oleksii Trekhleb

---

离题：你用绘图板画的吗？ - Geon George

@GeonGeorge 不，这个图是用笔绘制然后扫描的。 - Oleksii Trekhleb

这是我读过的关于组织 DP 的最佳答案之一。 - Ridhwaan Shakeel

这就是动态规划应该教授的方式！ - Stardust

Answer 3

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

分治：

1. 在子问题上执行更多的工作，因此需要更多的时间。
2. 在分治中，子问题相互独立。

动态规划：

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

- ASHWINI KOLEKAR

---

分治算法不一定比其动态规划的替代方案做更多的工作。一个例子是Erickson用于寻找最大算术进度的算法。 - Michael Foukarakis

Answer 4

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

著名的斐波那契数列即为例：

           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]                
    }
}

所以“分而治之”算法与递归有关。并且其中一些版本存在“具有相同参数的多个函数调用问题”。搜索“矩阵链乘法”和“最长公共子序列”等示例，需要使用DP来改进D&D算法的T(n)。

- A.B.

Answer 5

我假设您已经阅读了维基百科和其他学术资源，因此我不会重复这些信息。我必须声明我并不是计算机科学专家，但我会分享一下我对这些主题的理解...

动态规划

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

分治算法

这些算法通常解决类似问题的片段，然后在最后将它们组合起来。归并排序是分治算法的一个典型例子。与斐波那契的例子不同之处在于，在归并排序中，理论上可以任意划分，无论你如何切割，你仍然需要合并和排序。不论你如何划分数组，都需要完成相同的工作量来进行归并排序。求解fib(52)需要比求解fib(2) 更多的步骤。

- parker.sikand

Answer 6

我认为“分而治之”是一种递归方法，“动态规划”是一种填表方法。

例如，“归并排序”是一个“分而治之”的算法，因为在每个步骤中，你将数组分成两半，对这两半进行递归调用“归并排序”，然后将它们合并。

“背包问题”是一个“动态规划”的算法，因为你正在填写一个表示整个背包子问题最优解的表格。表格中的每个条目都对应于给定项1-j时，你可以在重量为w的袋子中携带的最大价值。

- ehuang

---

虽然这在很多情况下是正确的，但并不总是将子问题的结果存储在表中。 - Gokul

Answer 7

分治算法在每个递归级别上包含三个步骤：

1. 划分问题为子问题。
2. 通过递归地解决它们来征服子问题。
3. 将子问题的解组合成原问题的解。
   
   • 这是一种自顶向下的方法。
     
   • 它在子问题上执行更多的工作，因此具有更长的时间复杂度。
   • 例如，可以在O(2^n)时间复杂度内计算Fibonacci序列的第n项。
     
     

动态规划涉及以下四个步骤：

1. 定义最优解的结构。
2. 递归地定义最优解的值。
3. 计算最优解的值。
4. 从计算得到的信息中构造一个最优解。

• 这是一种自底向上的方法。
• 比分治算法消耗更少的时间，因为我们利用先前计算的值，而不是重新计算。
• 例如，可以在O(n)时间复杂度内计算Fibonacci序列的第n项。
  
  

为了更容易理解，让我们将分治算法视为暴力解决方案，将其优化为动态规划。

N.B. 只有具有重叠子问题的分治算法才能通过dp进行优化。

- Neel Alex

---

分治法是自底向上的，而动态规划是自顶向下的。 - Bahgat Mashaly

Answer 8

• 分治算法
  • 将问题拆分成不重叠的子问题
  • 例如：阶乘，即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))

如上所示，没有重复的fact(x)，因此阶乘具有不重叠的问题。

• 动态规划
  • 他们分成了重叠的子问题
  • 例如：斐波那契数列，即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中子问题的重复，我们可以将这些结果保存在表格中以节省计算量，这称为记忆化。

- ankit.rana

Answer 9

分治算法

• 这个问题可以通过以下三个步骤来解决： 1. 分割 - 分成若干子问题 2. 解决 - 通过递归地解决子问题 3. 合并 - 将子问题的解合并为原问题的解
• 递归方法
• 自顶向下技术
• 例子: 归并排序

动态规划

• 这个问题可以通过以下步骤来解决： 1. 定义最优解的结构 2. 反复定义最优解的值。 3. 自底向上地获取最优解的值。 4. 从获得的值中得到最终的最优解。
• 非递归
• 自底向上技术
• 例子: Strassen's矩阵乘法

- Tanvi Agarwal

---

你的答案是下面 @Neel Alex 的答案。!!!! - ibra

我在回答之前没有检查过，可能当时错过了。但是同样的问题可能会有相同的答案，因为有许多免费的在线学习资源可供使用。 - Tanvi Agarwal

Answer 10

分治算法:

这种算法包括三个阶段:

1. 将问题分解为更小的子问题
2. 征服，即解决这些较小的子问题
3. 合并这些子问题的解以获得最终答案。

动态规划:

DP是递归解决方案的优化。主要区别在于它存储子问题的解决方案，这些解决方案可以在找到剩余子问题的解决方案的过程中稍后访问。这样做是因为我们不必每次计算子问题的解决方案，而是可以简单地查找计算机内存以检索其值，前提是它已经被解决过了。我们可以将此作为递归的基本情况之一。例如，我们正在通过递归解决问题，我们可以将子问题的解决方案存储在数组中，并通过将相关代码添加到递归方法的其中一个基本情况中来访问它们。

DP有两种实现方式：

考虑一个问题：找到x的阶乘。

1. 表格法：我们使用自底向上的方法，即从最小的数字一直到x，以找到解决方案。

伪代码：

 1. int array
 2. for int=1, i<=x, i++
 3. array[i] = array[i-1]*i

记忆化：我们采用自顶向下的方法，即将问题分解成较小的部分并解决它们，以获得最终解决方案。

伪代码：

 fac():
 1. int array
 2. if(x==0): return 1
 3. if(array[x]!=null): return array[x]
 4. return array[x] = x*fac(x-1)

- Vishal Sharma