动态规划专题讲义课件.ppt

该【动态规划专题讲义课件 】是由【gxngqvk】上传分享，文档一共【74】页，该文档可以免费在线阅读，需要了解更多关于【动态规划专题讲义课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。动态规划专题讲义动态规划专题讲义1前言本文只是个人对动态规划的一些见解,理论性并不一定能保证正确,,理论性并不一定能保证正2动态规划是信息学竞赛中选手必须熟练掌握的一种算法,?,形式如下:**********找出从第一层到最后一层的一条路,,形式如下:back6数字三角形无论对与新手还是老手,这都是再熟悉不过的题了,很容易地,我们写出状态转移方程:f(i,j)=a[i,j]+min{f(i-1,j)+f(i-1,j+1)}对于动态规划算法解决这个问题,我们根据状态转移方程和状态转移方向,比较容易地写出动态规划的循环表示方法。但是,当状态和转移非常复杂的时候,也许写出循环式的动态规划就不是那么简单了。解决方法:back记忆化搜索数字三角形无论对与新手还是老手,这都是再熟悉不过的题了,很容7记忆化搜索我们尝试从正面的思路去分析问题,如上例,不难得出一个非常简单的递归过程: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记忆化搜索我们尝试从正面的思路去分析问题,如上例,不难得出一8记忆化搜索Opt[i,j]-每产生一个f(i,j),将f(i,j)的值放入opt中,以后再次调用到f(i,j)的时候,直接从opt[i,j]来取就可以了。于是动态规划的状态转移方程被直观地表示出来了,这样节省了思维的难度,减少了编程的技巧,而运行时间只是相差常数的复杂度,而且在相当多的情况下,递归算法能更好地避免浪费,[i,j]-每产生一个f(i,j),,