10.5　动态规划

动态规划（Dynamic Programming，DP）是运筹学的一个分支，是解决多阶段决策过程最优化的一种数学方法，主要用于以时间或地域为划分阶段的动态过程的最优化。

有一类活动的过程，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要做出决策，从而使整个过程达到最好的活动效果。

在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，这种解决多阶段决策最优化的过程称为动态规划方法。^[1]策略不同，效果也不同，多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使其在预定的标准下达到最好的效果。^[2]

由上述描述可知动态规划有以下几个主要特点：(https://www.daowen.com)

（1）可以把问题分解为不同阶段的多个子问题；

（2）后一个阶段子问题求解，依赖于前一个阶段的解；

（3）通过不同阶段的持续求解，选择一个最优解。