动态规划的原理?

动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,提出了著名的最优化原理(principle of optimality),把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法–动态规划。1957年出版了他的名著《Dynamic Programming》,这是该领域的第一本著作。
动态规划一般可分为线性动规,区域动规,树形动规,背包动规四类。举例:线性动规:拦截导弹,合唱队形,挖地雷,建学校,剑客决斗等;区域动规:石子合并, 加分二叉树,统计单词个数,炮兵布阵等;树形动规:贪吃的九头龙,二分查找树,聚会的欢乐,数字三角形等;背包问题:01背包问题,完全背包问题,多重背包问题,分组背包问题,二维背包,装箱问题,挤牛奶(同济ACM第1132题)等;

上一篇:macOS 下通过 pecl 命令安装 PHP 扩展 Swoole 方法


下一篇:Oracle Round 函式 (四捨五入)