极客教程贪婪方法与动态规划的区别
贪婪方法是一种算法范式，它逐个构建解决方案，总是选择下一个提供最明显和直接好处的部分。因此，选择局部最优也导致全局解决方案的问题最适合贪婪。
例如，考虑分数背包问题。局部最优策略是选择具有最大值与重量比的项目。这种策略也导致了全局最优解，因为我们允许取一个项目的一部分。
动态规划主要是对普通递归的优化。无论在哪里看到重复调用相同输入的递归解决方案，都可以使用动态规划对其进行优化。这个想法是简单地存储子问题的结果，这样我们就不必在以后需要时重新计算它们。这种简单的优化将时间复杂度从指数降低到多项式。例如，如果我们为斐波那契数写一个简单的递归解决方案，我们会得到指数时间复杂度，如果我们通过存储子问题的解决方案来优化它，时间复杂度会降低到线性。
以下是贪婪方法和动态规划之间的一些主要区别：
| 特征 | 贪心法 | 动态规划 |
|---|---|---|
| 可行性 | 在贪心算法中，我们会做出目前看起来最好的任何选择，希望它会导致全局最优解。 | 在动态规划中，我们在每一步都考虑当前问题和先前解决的子问题的解决方案来计算最优解。 |
| 最优性 | 贪心法中有时无法保证得到最优解。 | 保证动态规划将生成最佳解决方案，因为它通常会考虑所有可能的情况，然后选择最佳解决方案。 |
| 递归 | 贪心方法遵循在每个阶段做出局部最优选择的问题求解启发式。 | 动态规划是一种算法技术，通常基于使用一些先前计算的状态的循环公式。 |
| 记忆 | 它在记忆方面更有效，因为它从不回顾或修改以前的选择 | 它需要 dp 表进行记忆，它增加了它的记忆复杂性。 |
| 时间复杂度 | 贪心方法通常更快。例如，Dijkstra 的最短路径算法需要 O(ELogV + VLogV) 时间。 | 动态规划通常较慢。例如，Bellman Ford 算法需要 O(VE) 时间。 |
| 方式 | 贪心方法通过以连续向前的方式做出选择来计算其解决方案，从不回顾或修改以前的选择。 | 动态规划通过从较小的最优子解决方案综合它们来计算其解决方案自下而上或自上而下。 |
| 示例 | 分数背包 | 0/1 背包问题 |