在我使用这本书介绍设计与算法分析 ， 动态规划是说把重点放在最优性原则 “以优化问题的任何实例的最佳解决方案是由它的子实例最优解”。
然而， 贪婪的技术侧重于扩大部分构造的解决方案，直到你在一个完整的问题解决办法。 那么有人说，它必须是“上一步提供所有可行的选择中最好的地方选择”。
由于都涉及局部最优，是不是一个接一个的子集？
Answer 1:
动态规划适用于表现出的性能问题：
- 重叠子问题，并
- 最优子。
最优子意味着，你可以贪婪地解决子问题，并结合解决方案来解决更大的问题。 动态规划和贪婪算法之间的区别在于，用动态规划，有重叠子问题，并且这些子问题是使用记忆化来解决 。 “记忆化”是由此将子问题的解决方案被用来更迅速地解决其他子问题的技术。
这个答案已经得到了一定的关注，所以我会举一些例子。
考虑的问题“让改变与美元，镍和便士。” 这是一个贪婪的问题。 它具有最优子，因为你可以解决多少元。 然后，解决镍的数量。 然后便士的数量。 然后，您可以有效的解决方案相结合，这些子问题。 它并没有真正表现出重叠的子问题，因为解决每个子问题没有太大与其他人（也许有点）帮助。
考虑的问题“Fibonnaci数字。” 它表现出最优子，因为可以从F（9）和F解决F（10）（8）有效地（通过添加）。 这些子问题重叠，因为它们都共享F（7）。 如果你memoize的F的结果（7）当您解决F（8），你可以（9）更快地解决F。
在回答关于具有“重新考虑决定”做动态规划的评论：这显然不是任何线性动态规划算法像真正的最大子阵列的问题或以上的斐波那契问题。
从本质上讲，设想一个具有问题最优子为有向非循环图，其节点表示子问题（其中全问题通过其入度为零的节点表示），其向边代表子问题之间的依赖性。 然后，贪婪问题是一个树（除了根的所有节点具有单位入度）。 动态规划问题与入度大于一的某些节点。 这说明了重叠子问题。
Answer 2:
不同的是，动态编程需要你记住了小国的答案，而贪心算法是在这个意义上，所有需要的信息是在当前状态下的本地。 当然，有一些交集。
Answer 3:
关键的区别是贪心算法，在溶液中各地方可以选择，而无需了解所做的其他地方选择任何定案感组成的解决方案“静态”。 动态算法，但是，创建集的子问题的可能解决方案，只有当所有的子问题被认为是产生一个解决全球性问题。 该贪心算法的维基百科页面说得好：
由贪婪算法所做的选择可能取决于到目前为止，但没有对未来的选择或全部解决方案的子问题的选择。 它反复做一个贪婪的选择此起彼伏，减少每个给定的问题分解成较小的一个。 换句话说，贪婪算法从来没有重新考虑它的选择。 这是从动态规划，其内容详尽，并保证能找到解决方案的主要区别。 每一个阶段之后，动态规划使得基于前一阶段所做的所有决定的决定，并可能重新考虑解决前一阶段的算法路径。
Answer 4:
DP算法使用了（对于某些问题）的事实-尺寸的问题的最佳解决方案n由于尺寸的问题的最佳解决方案的n'<n并且使用该生成解决方案自下而上，从最小的问题所需要的尺寸。
它适合递归原理一样非常好（问题缩小到一个更小的子问题，并递归调用），而事实上 - DP解决方案通常表示为一个递推公式。
贪婪算法寻找一个局部点，并在这一点上做一些选择与数据。 对于某些问题（无例如negatve权最短路径） - 这个地方的选择将导致最佳的解决方案。
的两种方法之间的差异一个很好的例子是在最短路径问题 ：
- Dijsktra的算法是一个贪婪的方法（在每个步骤中，选择了它的路径是目前最小的节点-选择是基于算法的局部状态贪婪地完成）。
- Bellman-Ford算法是DP溶液（“放松” ALL边缘有效地减少了问题）
Answer 5:
贪婪的方法：
- 贪婪的方法侧重于扩大部分构造解决方案。
- 它提供了许多的结果，如可行的解决方案。
- 更高效
动态规划：
- 专注于最优化原理。
- 它提供了具体的答案。
- 效率较低
Answer 6:
DP和贪婪是DP之间的差异会寻找每个子问题的全局最优，但贪婪只会寻找局部最优。 所以，这对这样的场景：
假设你是在爬山的，和你想爬上尽可能高。 山上的路有几个分公司，并在每个路口，你需要决定采取哪一个分支，它是这个登山问题的子问题（我们的目标是一样的，只是起点不同）
对于贪心算法，你总是会选择哪一个似乎更陡了。 这是一个本地最优决策，并不能保证带来最好的结果
对于DP，在每个路口，你应该已经知道了海拔最高的每一个分支会导致你（假设你的评价顺序是相反的，又名从终点到起点），并选择具有最大高度。 这个决定是建立在未来的子问题的全局最优，并在那里将是这个子问题全球最佳
Answer 7:
贪婪和动态的解决方案的概念不是相互排斥的，我认为这是造成很多混乱的大多数答案。 我相信，在最重要的属性Amit的答案讲：一个贪婪的解决方案使得基于本地信息做出决策。 其结果是一个贪婪的解决方案最终可能会找到一个局部最优，而不是全球性的。 动态解决方案打破了问题成更小的子问题，然后汇总结果，以获得更大更复杂的问题的答案。 所以-这可能是一个问题，是动态和贪婪 ？ 答案是 - 是的，它是可能的。 一个例子是Dijkstra算法。 对于这个算法你做的每一步一个贪婪的选择，但你问题缩小到一个更简单的子问题。
不过也有不属于DP-S的贪心算法的例子：说爬山是一个贪婪算法不破的问题分成多个子问题 - 它始终只能解决一个。 也有不贪婪的DP的例子 - 例如在计算第n个Fibonacci数使用记忆化是不贪。
文章来源: How is dynamic programming different from greedy algorithms?
