1

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

 2 years ago
source link: https://www.jdon.com/57776
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
分而治之 (D&C) 和动态编程 (DP) 是伟大的算法

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. 重用这个值来计算较大的值

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK