Project1

标题: 【编程相关】动态规划到底是个啥 [打印本页]

作者: 羁绊的守望者 时间: 2014-11-3 19:24
标题: 【编程相关】动态规划到底是个啥
听说动态规划是个非常高端的东西，似乎可以根据情况不断地变动路线得到最优解……
但是某些时候又觉得挺好懂，比如01背包问题……
于是特来求教：动态规划到底是个啥，怎么用？@RyanBern @taroxd

作者: RyanBern 时间: 2014-11-3 19:34

数学模型2-1动态规划.pdf (1012 KB, 下载次数: 64)

不多解释了，我把我学动规时候的课件拿来，你可以看一看。
动态规划的特点是充分利用已经计算过的数据，达到节省空间的作用，通常都伴随递推。因此动态规划常用递归算法。
不过，由于要保存已经计算过的东西，所以DP实际上是拿空间换时间的一个计算手段。在内存比较廉价的今天，牺牲一些内存来换取效率是很明智的做法。

利用DP可以降低很多问题的复杂度，如果所求模型满足一个动态规划基本方程（无后效性），那么DP通常能把一个指数量级降低到多项式。不过，DP也不是万能的，例如著名的TSP问题，利用DP可以得到一个O(n*2^n)复杂度的算法，但是无法再降低了。

欢迎光临 Project1 (https://rpg.blue/)