我是谁?我从哪来?我要去哪?

0%

动态规划

什么是动态规划

动态规划是一个优化算法,由Richard E. Bellman教授在20世纪50年代发明并且引入到实际工程领域中,在广泛的领域中都有应用。

简单来说,动态规划就是把一个复杂的问题分解成很多简单的子问题,从所有的子问题的结果中搜寻这个复杂问题的最终结果。

比如有一个复杂的A问题,我们很难直接得到这个A问题的解决方案,于是我们把A问题拆解成B和C两个简单的子问题,得到B和C的结果之后,再通过分析这两个结果,得到最终A的答案。

举个通俗一点的例子就是老板给A派了很多活,A很累,于是A把这些活分解成简单的两个工作分配给了B和C,让他们俩帮帮忙,最后B和C完成工作之后,拿到他们的工作成果总结优化一下,变成自己的输出,交付给老板,工作就这样高效的做完了。

特性

动态规划也不是哪里都可以用的,想用动态规划解决问题,必须要具备以下三个条件:

最优子结构

一个问题可用通过他的子问题的最优解获得,这种结构的解法有时候也叫递归。如果想看一个问题能不能用动态规划,可以先看这个问题能不能分解成有最优解的子问题。

重叠子问题

一个子问题的结果可以被重复使用了很多次。比如刚才提到的例子,B和C收到A分派的活,但是C的活有一部分是B可以做的,所以B做完之后,C直接拿来用,就不用C自己做了,这样就减少了C的工作量。

无后效性

当达到之后的某种状态或者计算得到一个结果之后,这个状态或者结果就是确定的,不会因为其他的状态或者计算过程改变这个结果或者状态。B完成自己的工作,B的工作成果就是不会改变的,不管A和C怎么使用这个成果,B的结果就是最好的,B自己都不会去修改。

状态转移

状态转移公式是整个动态规划问题中的核心,整个动态规划的问题归根结底就是在寻找这个状态转移公式,就是从一个状态转移的到另外一个状态,而这个状态就是我们的数组dp,公式是用来计算dp中的每一个值。

比如在斐波那契数列问题中,状态可以直接定义成斐波那契数列的一个值,比如第2个斐波那契值也就是dp[2],想要到达状态dp[i]可以通过dp[i-1]dp[i-2]得到,根据数列的特点,斐波那契数列问题的状态转移方程可以定义为dp[i] = dp[i-1] + dp[i-2]。我们已经知道了基础状态的值dp[0]dp[1],通过状态转移方程可以得到任何一个斐波那契数值。

动态规划有点类似于数学里面的数学归纳法(先证明当n=1时命题成立,再假设n=m时命题成立推导出n=m+1时命题也成立),得到基础状态,假设已经知道了dp[m]m<n),求出dp[n]的值。

意义

动态规划的利用能大大减小时间复杂度,用人话说就是使用动态规划比不使用要节约很多很多很多的时间,随之而来的空间使用上的提升,不过这也特别好理解,毕竟现在时间越来越宝贵,而内存这种存储资源价格越来越低。

应用

  • 背包问题
  • 最短路径问题
  • 最长公共子序列问题
  • 航班或者机器人控制系统
  • CPU时间调度

参考文献

浅谈什么是动态规划以及相关的「股票」算法题
动态规划中的无后效性是什么意思?
Dynamic Programming (Components, Applications and Elements)
浅谈动态规划
算法-动态规划 Dynamic Programming—从菜鸟到老鸟
什么是动态规划(Dynamic Programming)?动态规划的意义是什么?
Dynamic programming
动态规划
动态规划算法学习总结

更多精彩内容请看我的个人博客