1/32
文档分类:IT计算机

ACM动态规划入门.ppt


下载后只包含 1 个 PPT 格式的文档,里面的视频和音频不保证可以播放,查看文件列表

特别说明:文档预览什么样,下载就是什么样。

下载所得到的文件列表
ACM动态规划入门.ppt
文档介绍:
ACM
1
2021/7/21
今天,
你 AC吗?
依然没有
2
2021/7/21
第四讲
动态规划入门
(Dynamic programming)
3
2021/7/21
一、经典问题:数塔问题
有形如下图所示的数塔,从顶部出发,在每一结点可以选择向左走或是向右走,一直走到底层,要求找出一条路径,使路径上的值最大。
4
2021/7/21
用暴力的方法,可以吗?
5
2021/7/21
这道题如果用枚举法(暴力思想),在数塔层数稍大的情况下(如31),则需要列举出的路径条数将是一个非常庞大的数目(2^30= 1024^3 > 10^9=10亿)。
试想一下:
6
2021/7/21
拒绝暴力,倡导和谐~
7
2021/7/21
从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值,只要左右两道路径上的最大值求出来了才能作出决策。
同样,下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去,直到倒数第二层时就非常明了。
如数字2,只要选择它下面较大值的结点19前进就可以了。所以实际求解时,可从底层开始,层层递进,最后得到最大值。
结论:自顶向下的分析,自底向上的计算。
考虑一下:
8
2021/7/21
二、经典问题:最长有序子序列
I
0
1
2
3
4
5
6
7
8
Num[I]
1
4
7
2
5
8
3
6
9
9
2021/7/21
解决方案:
I
0
1
2
3
4
5
6
7
8
Num[I]
1
4
7
2
5
8
3
6
9
F[I]
1
2
3
2
3
4
3
4
5
10
2021/7/21
内容来自淘豆网www.taodocs.com转载请标明出处.
相关文档
非法内容举报中心
文档信息
  • 页数32
  • 收藏数0 收藏
  • 顶次数0
  • 上传人fanglangjizv
  • 文件大小326 KB
  • 时间2021-07-21