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

该【动态规划专题讲义ppt课件 】是由【3827483】上传分享，文档一共【74】页，该文档可以免费在线阅读，需要了解更多关于【动态规划专题讲义ppt课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。动态规划专题讲义
Annual Work
Summary Report
2022 - 2023
#2022
前言
本文只是个人对动态规划的一些见解,理论性并不一定能保证正确,有不足和缺漏之处请谅解和及时地指出.
动态规划
动态规划
是信息学竞赛中选手必须熟练掌握的一种算法,他以其多元性广受出题者的喜爱.
2022 - 2023
#2022
目录
Catalogue
什么是动态规划
O1
一种确立状态的方法
三种特殊的动态规划
状态 阶段 决策
两种简单的动规武器
O2
O3
O4
O5
添加标题
添加标题
添加标题
什么是动态规划
?我们来下面的一个例子.
back
数字三角形
给你一个数字三角形, 形式如下:
单击此处添加正文，文字是您思想的提炼，为了演示发布的良好效果，请言简意赅地阐述您的观点。
1
3
5 6
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
01
02
记忆化搜索
back
Opt[i, j] - 每产生一个f(i, j)，将f(i, j)的值放入opt中，以后再次调用到f(i, j)的时候，直接从opt[i, j]来取就可以了。
于是动态规划的状态转移方程被直观地表示出来了，这样节省了思维的难度，减少了编程的技巧，而运行时间只是相差常数的复杂度，而且在相当多的情况下，递归算法能更好地避免浪费，在比赛中是非常实用的.
记忆化的功效
logo
动态规划的实质
记忆化搜索
可以看出动态规划的实质就是
,正符合了这个要求.