logo图片
数据结构与算法

动态规划

动态编程方法类似于分治法,将问题分解为越来越小的可能子问题。但与分而治之不同的是,这些子问题并不是独立解决的。相反,这些较小的子问题的结果会被记住并用于类似或重叠的子问题。
动态规划用于我们有问题的地方,可以将其划分为类似的子问题,以便它们的结果可以重用。大多数情况下,这些算法用于优化。在解决现有子问题之前,动态算法将尝试检查先前解决的子问题的结果。将子问题的解决方案组合起来,以达到最佳解决方案。
所以我们可以这么说-
问题应该能够被划分为更小的重叠子问题。 可以通过使用较小子问题的最优解来实现最优解。 动态算法使用记忆。

比较

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

示例

使用动态规划方法可以解决以下计算机问题-
斐波那契数列 背包问题(Knapsack Problem) 河内塔(Tower of Hanoi) Floyd-Warshall 全源最短路径算法 最短路径算法(shortest path)Dijkstra
动态编程可以以自上而下和自下而上的方式使用。当然,在大多数情况下,参考以前的解决方案输出比重新计算 CPU 周期要便宜。
昵称: 邮箱:
Copyright © 2020 立地货 All Rights Reserved.
备案号:京ICP备14037608号-4