文档介绍：前言
本文只是个人对动态规划的一些见解,理论性并不一定能保证正确,有不足和缺漏之处请谅解和及时地指出.
动态规划
是信息学竞赛中选手必须熟练掌握的一种算法,他以其多元性广受出题者的喜爱.
动态规划
目录
什么是动态规划
状态阶段决策
一种确立状态的方法
两种简单的动规武器
三种特殊的动态规划
什么是动态规划
?我们来下面的一个例子.
back
数字三角形
给你一个数字三角形, 形式如下:
1
2 3
4 5 6
7 8 9 10
找出从第一层到最后一层的一条
路,使得所经过的权值之和最小或
者最大.
back
数字三角形
无论对与新手还是老手,这都是再熟悉不过的题了,很容易地,我们写出状态转移方程:f(i, j)=a[i, j] + min{f(i-1, j)+f(i-1, j + 1)}
对于动态规划算法解决这个问题,我们根据状态转移方程和状态转移方向,比较容易地写出动态规划的循环表示方法。但是,当状态和转移非常复杂的时候,也许写出循环式的动态规划就不是那么简单了。
解决方法:
back
记忆化搜索
记忆化搜索
我们尝试从正面的思路去分析问题,如上例,不难得出一个非常简单的递归过程:
f1:=f(i-1,j+1); f2:=f(i-1,j);
if f1>f2 then f:=f1+a[i,j] else f:=f2+a[i,j];
显而易见,这个算法就是最简单的搜索算法。时间复杂度为2n,明显是会超时的。分析一下搜索的过程,实际上,很多调用都是不必要的,也就是把产生过的最优状态,又产生了一次。为了避免浪费,很显然,我们存放一个opt数组:
back
记忆化搜索
Opt[i, j] - 每产生一个f(i, j),将f(i, j)的值放入opt中,以后再次调用到f(i, j)的时候,直接从opt[i, j]来取就可以了。
于是动态规划的状态转移方程被直观地表示出来了,这样节省了思维的难度,减少了编程的技巧,而运行时间只是相差常数的复杂度,而且在相当多的情况下,递归算法能更好地避免浪费,在比赛中是非常实用的.
记忆化的功效
back
动态规划的实质
可以看出动态规划的实质就是
,正符合了这个要求.
记忆化搜索
状态阶段决策
或许有一种对动态规划的简单称法,,状态,决策这三者间得关系吧.
back