动态规划

动态编程方法类似于将问题分解为更小但更小的子问题的分而治之。但不同的是，分而治之，这些子问题并没有独立解决。相反，记住这些较小子问题的结果并用于类似或重叠的子问题。

动态编程用于我们遇到问题的地方，可以将其划分为类似的子问题，以便可以重复使用它们的结果。大多数情况下，这些算法用于优化。在解决现有子问题之前，动态算法将尝试检查先前解决的子问题的结果。结合子问题的解决方案以实现最佳解决方案。

所以我们可以说 -

  • 该问题应该能够分成较小的重叠子问题。
  • 通过使用较小子问题的最佳解决方案可以实现最佳解决方案。
  • 动态算法使用Memoization。

 

对照

与解决局部优化的贪婪算法相反，动态算法被激励用于问题的整体优化。

与分而治之的算法相比，其中解决方案被组合以实现整体解决方案，动态算法使用较小子问题的输出，然后尝试优化更大的子问题。动态算法使用Memoization来记住已经解决的子问题的输出。

例

使用动态编程方法可以解决以下计算机问题 -

  • 斐波纳契数系列
  • 背包问题
  • 河内塔
  • 由Floyd-Warshall完成的所有最短路径
  • Dijkstra的最短路径
  • 项目安排

动态编程可以自上而下和自下而上的方式使用。当然，大多数情况下，参考之前的解决方案输出比CPU周期重新计算更便宜。