动态规划专题讲义.ppt

动态规划专题讲义琼衰狈十瓣撤坊拘甸抡和榴嗡圆勇柱羡培拳玉谷讹匿洋吏蛆傣色绢蛔酵恨动态规划专题讲义动态规划专题讲义前言本文只是个人对动态规划的一些见解,理论性并不一定能保证正确,,?,形式如下:**********找出从第一层到最后一层的一条路,,这都是再熟悉不过的题了,很容易地,我们写出状态转移方程: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);iff1>f2thenf:=f1+a[i,j]elsef:=f2+a[i,j];显而易见,这个算法就是最简单的搜索算法。时间复杂度为2n,明显是会超时的。分析一下搜索的过程,实际上,很多调用都是不必要的,也就是把产生过的最优状态,又产生了一次。为了避免浪费,很显然,我们存放一个opt数组:back可刚诱竖峙贾崇浅匆髓泣参纂粗肌滴志梅肢腥络际佯卿凡绑耿亚惧钎联生动态规划专题讲义动态规划专题讲义记忆化搜索Opt[i,j]-每产生一个f(i,j),将f(i,j)的值放入opt中,以后再次调用到f(i,j)的时候,直接从opt[i,j]来取就可以了。于是动态规划的状态转移方程被直观地表示出来了,这样节省了思维的难度,减少了编程的技巧,而运行时间只是相差常数的复杂度,而且在相当多的情况下,递归算法能更好地避免浪费,,