动态规划中的最优性原理及方法的进一步研究.pdf

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划 是信息学竞赛中选手必须熟练掌握的一种算法,他以其多元性广受出题者的喜爱. 动态规划首次进入信息学奥赛是在IOI94（数字三角形），在国内首次出现是在NOI95。此后动态规划成为信息学奥赛的必考算法之一。