动态规划的应用场景有哪些？

本文共计5789个文字，预计阅读时间需要24分钟。

动态规划（DP）是一种多阶段决策过程的优化问题。在现实生活中，存在许多具有特殊性质的活动过程，由于它的特性，可以将过程分解为若干个相互关联的阶段。在每个阶段，需要做出决策，以实现整体的最优化。

动态规划（Dongtai PlanningDynamic Programming，简称DP）

多阶段决策过程的最优化问题

在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。当然，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线，这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题就称为多阶段决策问题。如下图所示：

多阶段决策过程，是指这样的一类特殊的活动过程，问题可以按时间顺序分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列。

基本概念

动态规划是解决 “多阶段决策问题”的一种高效算法。

动态规划是通过合理组合子问题的解从而解决整个问题解的过程。

动态规划是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。