动态规划专题讲义动态规划专题讲义前言前言?本文只是个人对动态规划的一些见解,理论性并不一定能保证正确,?是信息学竞赛中选手必须熟练掌握的一种算法,?什么是动态规划?状态阶段决策?一种确立状态的方法?两种简单的动规武器?三种特殊的动态规划什么是动态规划什么是动态规划???给你一个数字三角形, 形式如下: 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 f1>f2 then f:=f1+a[i,j] else f:=f2+a[i,j]; ?显而易见,这个算法就是最简单的搜索算法。时间复杂度为 2 n,明显是会超时的。分析一下搜索的过程, 实际上,很多调用都是不必要的, 也就是把产生过的最优状态,又产生了一次。为了避免浪费,很显然, 我们存放一个 opt 数组: 记忆化搜索记忆化搜索? Opt[i, j] - 每产生一个 f(i, j) , 将 f(i, j) 的值放入 opt 中,以后再次调用到 f(i, j) 的时候,直接从 opt[i, j] 来取就可以了。?于是动态规划的状态转移方程被直观地表示出来了,这样节省了思维的难度,减少了编程的技巧,而运行时间只是相差常数的复杂度,而且在相当多的情况下,递归算法能更好地避免浪费,在比赛中是非常实用的. 记忆化的功效动态规划的实质动态规划的实质?可以看出动态规划的实质就是?,正符合了这个要求.
动态规划教案 来自淘豆网m.daumloan.com转载请标明出处.
