其它技巧lecture动态规划课件.pptx
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《其它技巧lecture动态规划课件.pptx》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 其它 技巧 lecture 动态 规划 课件
- 资源描述:
-
1、2022-11-161今天,今天,你你 了吗?了吗?AC2022-11-162每周一星(每周一星(3):):混沌的云混沌的云Knight 2022-11-163第四讲第四讲动态规划动态规划(1)(1)(Dynamic programmingDynamic programming)2022-11-164先热身一下先热身一下2022-11-165(1466)计算直线的交点数计算直线的交点数问题描述:平面上有n条直线,且无三线共点,问这些直线能有多少种不同交点数。输入:n(n=20)输出:每个测试实例对应一行输出,从小到大列出所有相交方案,其中每个数为可能的交点数。样例输入4样例输出0 3 4 5
2、62022-11-166初步分析初步分析:我们知道我们知道:n n条直线互不平行且无三线共点的最多条直线互不平行且无三线共点的最多交点数交点数max=1+2+max=1+2+(n-1)=n(n-1)/2,(n-1)=n(n-1)/2,但本题不这么简单,因为问题问的是:但本题不这么简单,因为问题问的是:这些直线有这些直线有多少种多少种不同的交点数?不同的交点数?2022-11-167思考思考2分钟分钟:如何解决如何解决?2022-11-168然后,然后,假设假设=n-1 0+4=0+4*0+0=00+0=0;2 2、第四条与其中两条平行,交点数为、第四条与其中两条平行,交点数为0+(n-1)0+
3、(n-1)*1+0=3;1+0=3;3 3、第四条与其中一条平行,这两条平行直线和另外两点直线的交、第四条与其中一条平行,这两条平行直线和另外两点直线的交点数为点数为(n-2)(n-2)*2=4,2=4,而另外两条直线既可能平行也可能相交,因此而另外两条直线既可能平行也可能相交,因此可能交点数为:可能交点数为:0+0+(n-2n-2)*2+0=4 2+0=4 或者或者 0+(n-2)0+(n-2)*2+1=5 2+1=5 4 4、第四条直线不与任何一条直线平行,交点数为:第四条直线不与任何一条直线平行,交点数为:0+(n-3)0+(n-3)*3+0=3 3+0=3 或或0+(n-3)0+(n-
4、3)*3+2=5 3+2=5 或或0+0+(n-3)(n-3)*3+3=63+3=6即即n=4n=4时,有时,有0 0个,个,3 3个,个,4 4个,个,5 5个,个,6 6个不同交点数。个不同交点数。重点分析重点分析n的情况:的情况:2022-11-1611从上述从上述n=4n=4的分析过程中,我们发现:的分析过程中,我们发现:m m条直线的交点方案数条直线的交点方案数=(m-rm-r)条平行线与)条平行线与r r条直线交叉的交点数条直线交叉的交点数 +r+r条直线本身的交点方案条直线本身的交点方案=(m-rm-r)*r+rr+r条之间本身的交点方案数条之间本身的交点方案数(0=rm0=r
5、109=10亿)。试想一下:试想一下:2022-11-1615 拒绝拒绝暴力,暴力,倡导倡导和谐和谐2022-11-1616从顶点出发时到底向左走还是向右走应取决于是从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值,只要从左走能取到最大值还是从右走能取到最大值,只要左右两道路径上的最大值求出来了才能作出决策。左右两道路径上的最大值求出来了才能作出决策。同样,下一层的走向又要取决于再下一层上的最同样,下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去,大值是否已经求出才能决策。这样一层一层推下去,直到倒数第二层时就非常明了。直到倒数
6、第二层时就非常明了。如数字如数字2,只要选择它下面较大值的结点,只要选择它下面较大值的结点19前进就前进就可以了。所以实际求解时,可从底层开始,层层递进可以了。所以实际求解时,可从底层开始,层层递进,最后得到最大值。,最后得到最大值。结论:自顶向下的分析,自底向上的计算。结论:自顶向下的分析,自底向上的计算。考虑一下:考虑一下:2022-11-1617二、思考题:最长有序子序列二、思考题:最长有序子序列I012345678NumI1472583692022-11-1618解决方案:解决方案:I012345678NumI147258369FI1232343452022-11-1619三、三、11
展开阅读全文