开发手册 欢迎您!
软件开发者资料库

数据结构 - 动态规划

数据结构动态编程 - 使用c,C ++和Java学习数据结构和算法,从简单和简单的步骤开始,从基本到高级概念,包括概述,环境设置,算法,渐近分析,贪婪算法,分而治之,动态编程,数据结构,数组,链接列表,双链表,循环列表,堆栈,解析表达式,队列,优先级队列,线性,二进制,插值搜索,树,树遍历,二进制搜索树,B +,AVL,跨越,河内塔,哈希表,堆,图,深度,广度优先遍历,搜索技术,排序技术,排序算法,泡沫,合并排序算法,插入,选择,壳,快速排序,递归,斐波那契系列。

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

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

所以我们可以说 :

  • 问题应该可以分成较小的重叠子问题.

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

  • 动态算法使用Memoization.

比较

与贪婪算法相比,本地优化得到解决,动态算法可以促进问题的整体优化.

与分而治之的算法相比,在将解决方案组合在一起以实现整体解决方案的情况下,动态算法使用较小子问题的输出,然后尝试优化更大的子问题.动态算法使用Memoization来记住已经解决的子问题的输出.

示例

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

  • 斐波那契数字系列

  • 背包问题

  • 河内塔

  • Floyd-Warshall的所有最短路径

  • Dijkstra的最短路径

  • 项目调度

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