分而治之 (D&C) 和动态编程 (DP) 是伟大的算法 - Franc0

21-11-27 banq

Divide and Conquer (D&C:分而治之) 和Dynamic Programming (DP:动态编程)是伟大的算法技术,两者都将给定的问题分解为子问题并解决子问题(banq注:还原论 思维)。你如何选择它们来解决特定的问题呢?

要回答这个问题,您首先需要了解子问题是否重叠。如果它们不重叠,您应该使用分而治之。如果它们重叠,您应该使用动态编程 。

 

分而治之 (D&C) 

让我们考虑将问题 P 分解为 2 个较小的子问题 S1 和 S2。使用 D&C,您会:

  1. 分别解决S1和S2;
  2. 以某种方式组合它们两个S1和S2
  3. 得到答案结果P

一个经典的例子是归并排序,您可以通过以下方式对数组进行排序:

  1. 将其划分为 2 个子数组
  2. 对 2 个子数组进行独立 排序
  3. 合并已排序的子数组以获得原始排序

这是两个子问题没有重叠、没有相互依赖以找到解决方案。(banq:类似DDD有界上下文划分)

  

动态编程 (DP)

对于 DP,您需要意识到的第一件事是 S1 和 S2 重叠。这是什么意思 ?基本上,S1 和 S2 之间存在相互依赖关系。

假设 S2 依赖于 S1。这意味着必须先解决 S1,然后才能解决 S2。这正是 DP 在以自下而上的方式实施时所做的。

  1. 首先解决S1并记住结果。
  2. 利用 S1 的记忆结果求解 S2(S2 取决于 S1)
  3. 使用 S2 和 S1 的解求解 P。

您需要做的就是从底部 (S1) 开始并逐渐(通过 S2)向上 (P) 移动。

一个经典的例子是斐波那契数列:f(n) = f(n-1) + f(n-2)。f(n-1) 的解取决于 f(n-2) 的解。DP解决方案:

  1. 首先解决较小的数字的问题
  2. 重用这个值来计算较大的值
  3. 到最终值

 

1
猜你喜欢