最优化算法之动态规划入门

动态规划(英语:Dynamic programming,简称DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划常常适用于有重叠子问题和最优子结构性质的问题,动态规划方法所耗时间往往远少于朴素解法。

动态规划中包含三个重要子概念:

  • 最优子结构
  • 边界
  • 状态转移公式

对有重叠子问题和最优子结构性质的问题,在建模之后,即获得其状态转移公式和边界之后,可采用下列算法求解:

  • 递归求解
  • 备忘录算法
  • 动态规划求解

参考链接

  1. 动态规划,by wikipedia.
  2. 漫画:什么是动态规划?,by 程序员小灰.