算法分析 第五讲动态规划法

在实际生活中，有这么一类问题，它们的活动过程可以分为若干个阶段，而且在任一阶段i后的行为都仅依赖于i阶段的过程状态，而与i阶段之前的过程是如何达到i阶段的状态的方式无关，这样的过程就构成一个多阶段决策过程。在50年代，贝尔曼(RichardBellman)等人根据这类问题的多阶段决策的特性，提出了解决这类问题的“最优性原理”，从而创建了最优化问题的一种新的算法设计方法，称之为动态规划法。