贪婪方法 vs 动态编程
原文:https://www . geesforgeks . org/greedy-approach-vs-dynamic-programming/
A 贪婪算法是一种算法范式，它一点一点地建立一个解决方案，总是选择下一个能提供最明显和最直接好处的方案。因此，选择局部最优也导致全局解的问题最适合贪婪算法。
例如，考虑分数背包问题。局部最优策略是选择价值与重量比最大的项目。这个策略也导致了全局最优解，因为我们允许取一个项目的分数。
动态规划主要是对普通递归的优化。无论我们在哪里看到对相同输入重复调用的递归解决方案，我们都可以使用动态编程对其进行优化。这个想法是简单地存储子问题的结果，这样我们就不必在以后需要时重新计算它们。这种简单的优化减少了从指数到多项式的时间复杂性。例如，如果我们为斐波那契数写一个简单的递归解，我们得到指数时间复杂度，如果我们通过存储子问题的解来优化它，时间复杂度降低到线性。
下面是 Greedy 方法和动态规划的一些主要区别:
| 特征 | 贪婪方法 | 动态规划 | | --- | --- | --- | | **可行性** | 在贪婪算法中，我们会做出任何目前看来最好的选择，希望它能导致全局最优解。 | 在动态规划中，我们考虑当前问题和先前解决的子问题的解决方案，在每一步做出决策，以计算最优解。 | | **最优性** | 在贪婪方法中，有时不能保证得到最优解。 | 保证动态规划将产生一个最优解，因为它通常考虑所有可能的情况，然后选择最佳的。 | | **递归** | 贪婪方法遵循在每个阶段做出局部最优选择的问题求解启发式方法。 | 动态编程是一种算法技术，通常基于使用一些先前计算的状态的递归公式。 | | **记忆** | 它在记忆方面更有效，因为它从不回顾或修改以前的选择 | 它需要 dp 表进行记忆，增加了记忆的复杂性。 | | **时间复杂度** | 贪婪的方法通常更快。比如 [Dijkstra 的最短路径](https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/)算法需要 O(ELogV + VLogV)时间。 | 动态编程通常较慢。比如[贝尔曼福特算法](https://www.geeksforgeeks.org/bellman-ford-algorithm-simple-implementation/)需要 O(VE)时间。 | | **时尚** | 贪婪方法通过以连续向前的方式做出选择来计算它的解，从不回顾或修改以前的选择。 | 动态规划通过将较小的最优子解合成自下而上或自上而下地计算其解。 | | **例** | 分数背包。 | 0/1 背包问题 |版权属于：月萌API www.moonapi.com，转载请注明出处
