分而治之，动态编程和贪婪算法！

当我遇到最佳子结构的问题并且没有子问题共享子子问题时，可以使用分治法来解决吗？

是的，只要您可以为每种子问题找到最佳算法即可。

但是，当子问题共享子子问题（重叠子问题）时，我可以使用动态编程来解决问题吗？

这样对吗？

是。动态编程基本上是分而治之算法系列的一个特例，其中所有子问题都是相同的。

贪婪算法与动态编程有何相似之处？

他们是不同的。
动态编程为您提供了最佳解决方案。
贪婪算法通常会在很短的时间内给出良好/公平的解决方案，但是并不能保证达到最优。

可以 说
，这是相似的，因为它通常将解决方案构造分为几个阶段，在此阶段中，它会选择局部最优的选择。但是，如果阶段不是原始问题的最佳子结构，则通常不会导致最佳解决方案。

编辑：

正如@rrenaud指出的那样，有一些贪婪算法已被证明是最佳算法（例如Dijkstra，Kruskal，Prim等）。
因此，更正确地说，贪婪编程和动态编程之间的主要区别在于，前者在解决方案的空间上不是穷尽的，而后者在解决方案的空间上是穷尽的。
实际上，贪婪算法在该空间上是短视的，解决方案构建过程中所做的每个选择都不会被重新考虑。