算法:动态规划-动态规划

动态规划是研究一类最优化问题的方法，在经济、工程技术、企业管理、工农业生产及军事等领域中都有广泛的应用。近年来，在ACM/ICPC中，使用动态规划(或部分应用动态规划思维)求解的题不仅常见，而且形式也多种多样。而在与此相近的各类信息学竞赛中，应用动态规划解题已经成为一种趋势，这和动态规划的优势不无关系。 1、动态规划的常用名词 在学习动态规划之前，先得对下面的名词有所了解。本书将标准名词作了一些简化，便于大家更好的理解。 (1)状态(smte) 对于一个问题，所有可能到达的情况(包括初始情况和目标情况)都称为这个问题的一个状态。 (2)状态变量(sk) 对每个状态k关联一个状态变量sk，它的值表示状态k所对应的问题的当前解值。 (3)决策(decision) 决策是一种选择，对于每一个状态而言，你都可以选择某一种路线或方法，从而到达下一个状态。 (4)决策变量(dk) 在状态k下的决策变量dk的值表示对状态k当前所做出的决策。 (5)策略 策略是一个决策的集合，在我们解决问题的时候，我们将一系列决策记录下来，就是一个策略，其中满足某些最优条件的策略称之为最优策略。 (6)状态转移函数(t) 从一个状态到另一个状态，可以依据一定的规则来前进。我们用一个函数t来描述这样的规则，它将状态i和决策变量di映射到另一个状态j，记为t(i，di)=j (7)状态转移方程(f) 状态转移方程f描述了状态变量之间的数学关系。一般来说，与最优化问题相应，状态转移方程表示si的值最优化的条件，或者说是状态i所对应问题的最优解值的计算公式，用代数式表示就是： si=f({(sj,dj)|i=t(j,dj)，对决策变量dj所有可行的取值})