在我正在使用的《算法设计与分析简介》一书中， 动态编程 被认为专注于 最优性原理 ，“对任何优化问题实例的最优解决方案都包括对其子实例的最优解决方案”。
而 贪婪的技术则 专注于扩展部分构造的解决方案，直到您找到完整问题的解决方案为止。然后说，它必须是“该步骤中所有可行选择中的最佳本地选择”。
由于两者都涉及局部最优性，难道一个都不是另一个的子集吗？
动态编程适用于表现出以下特性的问题：
最佳子结构意味着您可以贪婪地解决子问题，并结合解决方案来解决更大的问题。 动态规划和贪婪算法之间的区别在于，动态规划中存在重叠的子问题，这些子问题使用备忘录来解决 。“备忘”是一种技术，通过该技术可以使用子问题的解决方案更快地解决其他子问题。
这个答案已经引起了人们的注意，因此我将举一些例子。
考虑问题“用美元，硬币和便士进行更改”。这是一个贪婪的问题。由于您可以求解美元数量，因此它具有最佳的子结构。然后，求出镍的数量。然后是几美分。然后，您可以将解决方案有效地结合到这些子问题上。它实际上并没有表现出重叠的子问题，因为解决每个子问题对其他子问题无济于事（也许有一点点）。
考虑问题“斐波那契数”。它具有最佳的子结构，因为您可以有效地（通过加法）从F（9）和F（8）求解F（10）。这些子问题重叠，因为它们都共享F（7）。如果您在求解F（8）时记住F（7）的结果，则可以更快地求解F（9）。
回应有关动态规划的评论与“重新考虑决策”有关：对于任何线性动态规划算法（例如最大子数组问题或上面的斐波那契问题），显然不是这样。
本质上，将具有最佳子结构的问题想象为有向无环图，该无向图的节点表示子问题（其中整个问题由度数为零的节点表示），并且有向边表示子问题之间的依存关系。然后，一个贪婪的问题是一棵树（除了根节点之外的所有节点都有单位度）。一个动态编程问题具有一些度数大于1的节点。这说明了重叠的子问题。
