下载此文档

《c案例04动态规划》.ppt


文档分类:管理/人力资源 | 页数:约57页 举报非法文档有奖
1/57
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/57 下载此文档
文档列表 文档介绍
第四讲
动态规划
(Dynamic programming)
Date
1
整理课件
一、经典问题:数塔问题
有形如下图所示的数塔,从顶部出发,在每一结点可以选择向左走或是向右走,一直走到底层,要求找出一条路径,使路径上的值最大。
Date
2
整理课件
用暴力的方法,可以吗?
Date
3
整理课件
这道题如果用枚举法(暴力思想),在数塔层数稍大的情况下(如31),则需要列举出的路径条数将是一个非常庞大的数目(2^30= 1024^3 > 10^9=10亿)。
试想一下:
Date
4
整理课件
拒绝暴力,倡导和谐~
Date
5
整理课件
从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值,只要左右两道路径上的最大值求出来了才能作出决策。
同样,下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去,直到倒数第二层时就非常明了。
如数字2,只要选择它下面较大值的结点19前进就可以了。所以实际求解时,可从底层开始,层层递进,最后得到最大值。
结论:自顶向下的分析,自底向上的计算。
考虑一下:
Date
6
整理课件
思路:从倒数第二行起, 按照状态转移方程
dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + val[i][j]
向上递推, 直到val[1][1], 此时dp[1][1]就是结果
Date
7
整理课件
二、经典问题:最长有序子序列
[问题描述]     找出由n个元素组成的序列的最长有序子序列长度及其中一个最长有序子序列 (注:这里有序指非递减顺序,且不要求子序列连续)。 例如,对于序列[3, 7, 1, 5, 9, 3],其中最长有序子序列长度为3,这样的子序列有: [3, 7, 9]、[1, 5, 9]、[3, 5, 9]。
Date
8
整理课件
二、经典问题:最长有序子序列
Date
9
整理课件
二、经典问题:最长有序子序列
Date
10
整理课件

《c案例04动态规划》 来自淘豆网www.taodocs.com转载请标明出处.

相关文档 更多>>
非法内容举报中心
文档信息
  • 页数57
  • 收藏数0 收藏
  • 顶次数0
  • 上传人相惜
  • 文件大小468 KB
  • 时间2022-07-31