【编程相关】动态规划到底是个啥

羁绊的守望者

听说动态规划是个非常高端的东西，似乎可以根据情况不断地变动路线得到最优解……
但是某些时候又觉得挺好懂，比如01背包问题……
于是特来求教：动态规划到底是个啥，怎么用？@RyanBern @taroxd  

RyanBern

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

2014-11-3 19:28 上传

点击文件名下载附件

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

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