数据结构&算法 动态规划

• 

  动态规划

  在动态规划方法类似于将问题分解为越来越小的可能的子问题的分治算法。但是与分治算法不同，这些子问题不是独立解决的。相反，这些较小的子问题的结果将被记住并用于相似或重叠的子问题。在有问题的地方使用动态规划，可以将其分为相似的子问题，以便其结果可以重复使用。通常，这些算法用于优化。在解决现有子问题之前，动态规划将尝试检查先前解决的子问题的结果。将子问题的解决方案组合在一起，以获得最佳解决方案。

  所以我们可以说-

  • 该问题应能够分为较小的重叠子问题。
  • 通过使用较小的子问题的最佳解决方案，可以实现最佳解决方案。
  • 动态规划算法使用记忆化。
• 

  比较方式

  与解决局部优化的贪婪算法相反，动态规划算法是针对问题的整体优化的目的。与将解决方案结合起来以实现整体解决方案的分而治之算法相反，动态算法使用较小子问题的输出，然后尝试优化较大子问题。动态算法使用记忆来记住已经解决的子问题的输出。
• 

  例子

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

  • 斐波那契数列
  • 背包问题
  • 汉诺塔
  • 两人最短路径
  • Dijkstra最短路径
  • 项目调度