动态规划基础教程文档

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

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

所以我们可以这么说-

与解决局部优化的贪心算法相比，动态算法的动机是对问题进行整体优化。

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

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

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