动态规划的基本定理和基本方程

　　动态规划发展的早期阶段，从简单逻辑出发给出了所谓最优性原理，然后在最优策略存在的前提下导出基本方程，再由这个方程求解最优策略。后来在动态规划的应用过程中发现，最优性原理不是对任何决策过程普遍成立，它与基本方程不是无条件等价，二者之间也不存在任何确定的蕴含关系。基本方程在动态规划中起着更为本质的作用。

　　对于初始状态，策略是最优策略的充要条件是对于任意的k,,有

　　

　　若是最优策略，则对于任意的k,1<k<n，它的子策略对于由x1和确定的以为起点的第k到n后部子过程而言，也是最优策略。

　　上述推论称为最优化原理，它给出了最优策略的必要条件，通常略述为：不论过去的状态和决策如何，对于前面的决策形成的当前的状态而言，余下的各个决策必定构成最优策略。

　　根据基本定理的推论可以得到动态规划的基本方程：

　　(1)

　　其中fn + 1(xn + 1) = δ(xn + 1)是决策过程的终端条件，δ为一个已知函数。当xn + 1只取固定的状态时称固定终端；当xn + 1可在终端集合Xn + 1中变动时称自由终端。最终要求的最优指标函数满足(2)式：

　　(2)

　　(1)式是一个递归公式，如果目标状态确定，当然可以直接利用该公式递归求出最优值（这种递归方法将在后文介绍，称作备忘录法），但是一般在实际应用中我们通常将该递归公式改为递推公式求解，这样一般效率会更高一些。