贪婪方法与动态规划的区别
在这篇文章中，我们将了解贪婪算法和动态编程方法之间的区别。
贪心算法
它是一种算法范式，它逐步地建立在解决方案上。选择下一步，以便它给出最明显和最直接的好处。
涉及选择局部最优值的问题将有助于选择全局最优值/问题的解决方案。这样就解决了与贪婪算法相关的问题。
不能确定贪婪算法会导致最佳解决方案。
在问题的每个阶段都会做出最佳选择，i.e即局部最佳解决方案。
就内存使用而言，它是高效的，因为不必回溯或更改以前的解决方案/值。
通常，与动态编程技术相比，它们速度更快。
示例：Dijkstra的最短路径算法需要O（ELogV+VLogV）时间。
贪婪算法中的解决方案是以正向方法计算的，永远不会访问先前的值/解决方案或对其进行更改。
动态编程
这是一种优化技术，可帮助存储子问题的结果，以便将来在需要时无需重新计算它们。可以从预先计算的集合中提取它们。它将时间复杂度从指数复杂度降低到多项式复杂度。
例如：递归解决方案可以通过计算转化为动态编程问题。
在这种情况下，通过考虑当前的问题以及先前解决的总和问题的解决方案，可以做出每个步骤的决策。这将用于计算最佳值/解决方案。
可以保证动态编程问题的解决方案将是最佳的解决方案。
在这里，选择的最佳解决方案是全局最佳解决方案。它使用某些公式来存储先前计算的状态值。
动态编程表是存储所必需的。这增加了存储器的复杂性。
它相对较慢。
示例：需要O(VE)时间的BellmanFord算法。
动态编程通过自下而上或自上而下的方法来确定解决方案，方法是从具有最佳解决方案的较小问题中发展出来。