动态编程（Dynamic Programming）

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

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

所以我们可以说 -

• 该问题应该能够分成较小的重叠子问题。

• 通过使用较小子问题的最佳解决方案可以实现最佳解决方案。

• 动态算法使用Memoization。

比较(Comparison)

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

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

例子 (Example)

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

• 斐波纳契数系列
• 背包问题
• Tower of Hanoi
• 由Floyd-Warshall完成的所有最短路径
• Shortest path by Dijkstra
• Project scheduling

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