动态规划_____浙江大学_acm程序设计竞赛_动态规划讲义.pdf

动态规划专题讲义 本文只是个人对动态规划的一 些见解,理论性并不一定能保证 言 前 正确,有不足和缺漏之处请谅解 和及时地指出.  是信息学竞赛中选手必 划 规 态 动 须熟练掌握的一种算法,他以其 多元性广受出题者的喜爱.  什么是动态规划 状态 阶段 决策 录 目  一种确立状态的方法  两种简单的动规武器  三种特殊的动态规划 划 规 态 动 是 么 什 在学习动态规划之前你一定学 过有哪些信誉好的足球投注网站.那么有哪些信誉好的足球投注网站与动态规划有 什么关系呢?我们来下面的一 个例子. 给你一个数字三角形, 形式如下: 1 形 角 三 字 数 2 3 4 5 6 7 8 9 10 找出从第一层到最后一层的一条 路,使得所经过的权值之和最小或 者最大.  无论对与新手还是老手，这都是再 熟悉不过的题了，很容易地，我们 写出状态转移方程：f(i, j)=a[i, j] 形 角 三 字 数 + min{f(i-1, j)+f(i-1, j + 1)}  对于动态规划算法解决这个问题， 我们根据状态转移方程和状态转移 方向，比较容易地写出动态规划的 循环表示方法。但是，当状态和转 移非常复杂的时候，也许写出循环 式的动态规划就不是那么简单了。  解决方法：  我们尝试从正面的思路去分析问题， 如上例，不难得出一个非常简单的 递归过程: 索 搜 化 忆 记  f1:=f(i-1,j+1); f2:=f(i-1,j);  if f1f2 then f:=f1+a[i,j] else f:=f2+a[i,j];