常用算法笔记 > 动态规划
动态规划思想和使用限制

动态规划英文 Dynamic Programming,是求解决策过程最优化的数学方法,后来沿用到了编程领域。

动态规划的大致思路是把一个复杂的问题转化成一个分阶段逐步递推的过程,从简单的初始状态一步一步递推,最终得到复杂问题的最优解。

动态规划解决问题的过程分为两步:

  1. 寻找状态转移方程  

  2. 确定初始边界条件

  3. 利用状态转移方程式 从初始化条件一步步推导到最终结果

用动态规划需要满足条件:

1.最优化原理(最优子结构性质) 最优化原理可这样阐述:一个最优化策略具有这样的性质,不论过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简而言之,一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。

2.无后效性将各阶段按照一定的次序排列好之后,对于某个给定的阶段状态,它以前各阶段的状态无法直接影响它未来的决策,而只能通过当前的这个状态。换句话说,每个状态都是过去历史的一个完整总结。这就是无后向性,又称为无后效性。