这三种算法非常相似，但是又有一些区别，理解如下：
-
分治：
把一个问题划分为若干子问题，求出子问题的最优解，再把子问题的最优解进行merge，最终得到原问题的最优解
-
动态规划；
原问题的最优解包含子问题的最优解（即，拥有最优子结构），同时，求子问题的最优解过程是存在重复的（即，子问题重叠），而分治法的子问题之间是独立的，不存在重复。这种case需要用动态规划来求解
-
贪心算法：
和动态规划类似，但是通过局部最优达到全局最优，而动态规划求解的是全局最优。贪心算法是自顶向下的求解过程。
贪心算法只需考虑一个选择（亦即，贪心的选择）；在做贪心选择时，子问题之一必须是空的，因此只留下一个非空子问题。 贪心算法与动态规划与很多相似之处。特别地，贪心算法适用的问题也是最优子结构。贪心算法与动态规划有一个显著的区别，就是贪心算法中，是以自顶向下的方式使用最优子结构的。贪心算法会先做选择，在当时看起来是最优的选择，然后再求解一个结果子问题，而不是先寻找子问题的最优解，然后再做选择。
贪心算法是通过做一系列的选择来给出某一问题的最优解。对算法中的每一个决策点，做一个当时看起来是最佳的选择。这一点是贪心算法不同于动态规划之处。在动态规划中，每一步都要做出选择，但是这些选择依赖于子问题的解。因此，解动态规划问题一般是自底向上，从小子问题处理至大子问题。贪心算法所做的当前选择可能要依赖于已经做出的所有选择，但不依赖于有待于做出的选择或子问题的解。因此，贪心算法通常是自顶向下地做出贪心选择，不断地将给定的问题实例归约为更小的问题。贪心算法划分子问题的结果，通常是仅存在一个非空的子问题。
如何判断什么时候使用贪心算法或者动态规划？?
状态转移树中，若后一状态仅仅取决于上一个状态，就用贪婪算法；若后一状态取决于之前的多个状态，就用动态规划
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
