贪婪方法与动态规划的区别

在这篇文章中，我们将了解贪婪算法和动态编程方法之间的区别。

贪心算法

它是一种算法范式，它逐步地建立在解决方案上。选择下一步，以便它给出最明显和最直接的好处。

• 涉及选择局部最优值的问题将有助于选择全局最优值/问题的解决方案。这样就解决了与贪婪算法相关的问题。

• 不能确定贪婪算法会导致最佳解决方案。

• 在问题的每个阶段都会做出最佳选择，i.e即局部最佳解决方案。

• 就内存使用而言，它是高效的，因为不必回溯或更改以前的解决方案/值。

• 通常，与动态编程技术相比，它们速度更快。

• 示例：Dijkstra的最短路径算法需要O（ELogV + VLogV）时间。

• 贪婪算法中的解决方案是以正向方法计算的，永远不会访问先前的值/解决方案或对其进行更改。

动态编程

这是一种优化技术，可帮助存储子问题的结果，以便将来在需要时无需重新计算它们。可以从预先计算的集合中提取它们。它将时间复杂度从指数复杂度降低到多项式复杂度。 

• 例如：递归解决方案可以通过计算转化为动态编程问题。

• 在这种情况下，通过考虑当前的问题以及先前解决的总和问题的解决方案，可以做出每个步骤的决策。这将用于计算最佳值/解决方案。

• 可以保证动态编程问题的解决方案将是最佳的解决方案。

• 在这里，选择的最佳解决方案是全局最佳解决方案。它使用某些公式来存储先前计算的状态值。

• 动态编程表是存储所必需的。这增加了存储器的复杂性。

• 它相对较慢。

• 示例：需要O(VE)时间的Bellman Ford算法。

• 动态编程通过自下而上或自上而下的方法来确定解决方案，方法是从具有最佳解决方案的较小问题中发展出来。