动态编程与贪婪算法有何不同？

动态编程适用于表现出以下特性的问题：

• 重叠的子问题，以及
• 最佳子结构。

最佳子结构意味着您可以贪婪地解决子问题，并结合解决方案来解决更大的问题。
动态规划和贪婪算法之间的区别在于，动态规划中存在重叠的子问题，这些子问题使用备忘录来解决
。“备忘”是一种技术，通过该技术可以使用子问题的解决方案更快地解决其他子问题。

这个答案已经引起了人们的注意，因此我将举一些例子。

考虑问题“用美元，硬币和便士进行更改”。这是一个贪婪的问题。由于您可以求解美元数量，因此它具有最佳的子结构。然后，求出镍的数量。然后是几美分。然后，您可以将解决方案有效地结合到这些子问题上。它实际上并没有表现出重叠的子问题，因为解决每个子问题对其他子问题无济于事（也许有一点点）。

考虑问题“斐波那契数”。它具有最佳的子结构，因为您可以有效地（通过加法）从F（9）和F（8）求解F（10）。这些子问题重叠，因为它们都共享F（7）。如果您在求解F（8）时记住F（7）的结果，则可以更快地求解F（9）。

回应有关动态规划的评论与“重新考虑决策”有关：对于任何线性动态规划算法（例如最大子数组问题或上面的斐波那契问题），显然不是这样。

本质上，将具有最佳子结构的问题想象为有向无环图，该无向图的节点表示子问题（其中整个问题由度数为零的节点表示），并且有向边表示子问题之间的依存关系。然后，一个贪婪的问题是一棵树（除了根节点之外的所有节点都有单位度）。一个动态编程问题具有一些度数大于1的节点。这说明了重叠的子问题。