第十二讲 动态规划
（教材： 第十二章 动态规划）
一. 应用动态规划解决问题的思路
二. 动态规划解决问题的基本步骤
三. 动态规划解题的简单例子
本讲的学习不要停留在抽象的概念、步骤的记忆, 而应该通过教材中的具体例子切实领会动态方法的要点和方法。
一. 应用动态规划解决问题的思路
动态规划是一种多阶段的决策方法。这种方法把要解决的问题划分为若干阶段， 在每一个阶段中， 要求对各种不同的状态下找出“最佳的对策”，然后确定整个问题的“最佳策略”。
动态规划解决多阶段决策问题的思想基于下面的想法:
假设图中从
到 
的最短路线是 
， 那么从 
到 
的所有可能的路线中， 
必定是其中最短的一条.
同样， 从 
到 
的所有可能的路线中， 
必定是其中最短的一条。换言之， 整体最优中的一部分， 也必定是相应局部中的最优.
二. 动态规划解决问题的基本步骤
应用动态规划解决实际问题的基本步骤可以简述为：
（1） 划分阶段；
（2） 确定状态变量和决策变量；
（3） 确定状态转移规律；
（4） 确定直接指标和最优后部过程指标；
（5） 确定最优后部过程指标的递推方程.