Divide and Conquer (D&C：分而治之) 和Dynamic Programming (DP：动态编程)是伟大的算法技术，两者都将给定的问题分解为子问题并解决子问题（banq注：还原论 思维）。你如何选择它们来解决特定的问题呢？
要回答这个问题，您首先需要了解子问题是否重叠。如果它们不重叠，您应该使用分而治之。如果它们重叠，您应该使用动态编程 。
分而治之 (D&C)
让我们考虑将问题 P 分解为 2 个较小的子问题 S1 和 S2。使用 D&C，您会：
- 分别解决S1和S2；
- 以某种方式组合它们两个S1和S2
- 得到答案结果P
一个经典的例子是归并排序，您可以通过以下方式对数组进行排序：
- 将其划分为 2 个子数组
- 对 2 个子数组进行独立 排序
- 合并已排序的子数组以获得原始排序
这是两个子问题没有重叠、没有相互依赖以找到解决方案。（banq：类似DDD有界上下文划分）
动态编程 (DP)
对于 DP，您需要意识到的第一件事是 S1 和 S2 重叠。这是什么意思 ？基本上，S1 和 S2 之间存在相互依赖关系。
假设 S2 依赖于 S1。这意味着必须先解决 S1，然后才能解决 S2。这正是 DP 在以自下而上的方式实施时所做的。
- 首先解决S1并记住结果。
- 利用 S1 的记忆结果求解 S2（S2 取决于 S1）
- 使用 S2 和 S1 的解求解 P。
您需要做的就是从底部 (S1) 开始并逐渐（通过 S2）向上 (P) 移动。
一个经典的例子是斐波那契数列：f(n) = f(n-1) + f(n-2)。f(n-1) 的解取决于 f(n-2) 的解。DP解决方案：
- 首先解决较小的数字的问题
- 重用这个值来计算较大的值
- 到最终值