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

6 回答

• 17

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

  分而治之：

  • 更多地处理子问题，因此有更多的时间消耗 .

  • 在分而治之中，子问题是相互独立的 .

  动态编程：

  • 仅解决子问题一次，然后将其存储在表中 .

  • 在动态编程中，子问题不是独立的 .

  回复于 2024-05-05T06:36:51+08:00
• 5

  Divide and Conquer

  Divide and Conquer的工作原理是将问题分解为子问题，递归地克服每个子问题并组合这些解决方案 .

  Dynamic Programming

  动态编程是一种解决重叠子问题的技术 . 每个子问题仅解决一次，并且每个子问题的结果存储在表（通常实现为数组或散列表）中以供将来引用 . 这些子解决方案可用于获得原始解决方案，并且存储子问题解决方案的技术称为存储器化 .

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

  理解差异的一个典型例子是看到这两种获得第n个斐波纳契数的方法 . 从麻省理工学院查看material .

  ---

  Divide and Conquer approach
  

  Dynamic Programming Approach
  

  回复于 2024-05-05T06:36:51+08:00
• 117

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

  着名的例子斐波那契数字：

  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
  

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

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

  // 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）的示例的“矩阵链乘法”和“最长公共子序列” .

  回复于 2024-05-05T06:36:51+08:00
• 8

  我假设您已经阅读过维基百科及其他学术资源，因此我不会回收任何这些信息 . 我还必须指出，我不是一个计算机科学专家，但我会分享我对这些主题的理解 .

  动态编程

  将问题分解为离散的子问题 . Fibonacci序列的递归算法是动态规划的一个例子，因为它通过首先求解fib（n-1）来求解fib（n） . 为了解决原始问题，它解决了一个不同的问题 .

  分而治之

  这些算法通常解决问题的类似部分，然后将它们放在一起 . Mergesort是分而治之的典型例子 . 这个例子与Fibonacci例子的主要区别在于，在mergesort中，除法可以（理论上）是任意的，无论你如何对它进行分割，你仍然在合并和排序 . 无论你如何分割数组，都必须完成相同数量的工作来合并数组 . 解决fib（52）需要比解决fib（2）更多的步骤 .

  回复于 2024-05-05T06:36:51+08:00
• 4

  我认为 Divide & Conquer 是一种递归方法， Dynamic Programming 作为表填充 .

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

  Knapsack 是一个 Dynamic Programming 算法，因为您正在填充一个表，表示整个背包的子问题的最佳解决方案 . 表中的每个条目对应于您可以携带的最大值给予物品1-j的重量袋 .

  回复于 2024-05-05T06:36:51+08:00
• 17

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

  正如我现在所看到的，我可以说 dynamic programming is an extension of divide and conquer paradigm .

  我不会将它们视为完全不同的东西 . 因为 they both work by recursively breaking down a problem into two or more sub-problems 的相同或相关类型，直到这些变得简单到可以直接解决 . 然后组合子问题的解决方案以给出原始问题的解决方案 .

  那么为什么我们仍然有不同的范式名称以及为什么我将动态编程称为扩展 . 这是因为动态编程方法可能适用于问题 only if the problem has certain restrictions or prerequisites . 之后，动态编程通过 memoization 或 tabulation 技术扩展了分而治之的方法 .

  我们一步一步走......

  动态编程先决条件/限制

  正如我们刚刚发现的那样，为了使动态编程适用，有两个关键属性可以划分和征服问题：

  • Optimal substructure - 可以从其子问题的最优解构建最优解

  • Overlapping sub-problems - 问题可以分解为多次重复使用的子问题，或者问题的递归算法一遍又一遍地解决相同的子问题，而不是总是生成新的子问题

  一旦满足这两个条件，我们可以说使用动态编程方法可以解决这种分而治之的问题 .

  分治的动态编程扩展

  动态编程方法通过两种技术（ memoization 和 tabulation ）扩展了分而治之的方法，这两种技术都有存储和重用子问题解决方案的目的，这些解决方案可以大大提高性能 . 例如，Fibonacci函数的天真递归实现具有 O(2^n) 的时间复杂度，其中DP解决方案仅使用 O(n) 时间执行相同操作 .

  Memoization (top-down cache filling) 指的是缓存和重用先前计算结果的技术 . 因此，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]
  }
  

  Tabulation (bottom-up cache filling) 类似，但侧重于填充缓存的条目 . 迭代地计算缓存中的值是最容易的 . 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先决条件及其方法，我们已准备好将上面提到的所有内容放在一张图片中 .

  

  如果您想查看代码示例，可以查看more detailed explanation here，您可以在其中找到两个算法示例：二进制搜索和最小编辑距离（Levenshtein距离），它们说明了DP和DC之间的差异 .

  回复于 2024-05-05T06:36:51+08:00