没有合适的资源？快使用搜索试试~ 我知道了~

文库首页课程资源专业指导动态规划基础讲解及经典案例分析

动态规划基础讲解及经典案例分析

动态规划

需积分: 48 11 下载量 12 浏览量 2012-07-21 15:15:49 上传评论 2 收藏 624KB PPT 举报

温馨提示

试读

60页

介绍了动态规划的原理，与常见几个动态规划实例。其中包含了几个经典动态规划算法的c语言代码。

资源推荐

资源详情

资源评论

21/8/4 1

第九课

动态规划 (I)

综合实践考核

数字三角形

1 、问题描述

上图给出了一个数字三角形。从三角形的顶部到底部有很多条

不同的路径。对于每条路径，把路径上面的数加起来可以得到

一个和，和最大的路径称为最佳路径。你的任务就是求出最佳

路径上的数字之和。

注意：路径上的每一步只能从一个数走到下一层上和它最近的

左边的数或者右边的数。

问题描述

输入数据

输入的第一行是一个整数 N (1 < N <= 100) ，给出三

角形的行数。下面的 N 行给出数字三角形。数字三

角形上的数的范围都在 0 和 100 之间。

输出要求

输出最大的和。

问题描述

输入样例

3 8

8 1 0

2 7 4 4

4 5 2 6 5

输出样例

2 、解题思路

这道题目可以用递归的方法解决。基本思路是：

以 D( r, j) 表示第 r 行第 j 个数字 (r ， j 都从 1 开始算 ) ，以

MaxSum(r, j) 代表从第 r 行的第 j 个数字到底边的最佳路径

的数字之和，则本题是要求 MaxSum(1, 1) 。

从某个 D(r, j) 出发，显然下一步只能走 D(r+1, j) 或者 D(r+1, j+

1) 。如果走 D(r+1, j) ，那么得到的 MaxSum(r, j) 就是 MaxSum

(r+1, j) + D(r, j) ；如果走 D(r+1, j+1) ，那么得到的

MaxSum(r, j) 就是 MaxSum(r+1, j+1) + D(r, j) 。所

以，选择往哪里走，就看 MaxSum(r+1, j) 和 MaxSum(r+1, j+

1) 哪个更大了。

剩余59页未读，继续阅读

评论收藏

内容反馈

资源评论

资源反馈

评论星级较低，若资源使用遇到问题可联系上传者，3个工作日内问题未解决可申请退款~

dhy012345

粉丝: 8
资源: 3

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

动态规划基础讲解及经典案例分析

动态规划算法经典例题

动态规划的列子 几个案例

动态规划一些经典实例的代码

经典算法——动态规划教程

动态规划算法经典题目

动态规划算法案例实现

动态规划算法学习十例之三

动态规划算法——C++实现经典案例——初级动态规划算法——C++实现经典案例——初级

动态规划算法原理及例子

动态规划与最优控制模型

动态规划基础讲解及经典案例分析解答

进位制基础讲解及经典案例分析

搜索技术基础讲解及经典案例分析

高精度计算基础讲解及经典案例分析解答

《绝了!Excel可以这样用:数据分析经典案例实战图表书》高宏 著

《SAS开发经典案例解析》杨池然 (1).rar

Python超级实用小案例（最全讲解）

ASP.NET2.0O数据库开发经典案例光盘

《分布式系统常用技术及案例分析》 PDF

ecshop二次开发 47个经典插件开发案例 讲解很详细 学习参考感谢提供者

开源企业级大数据开发经典实战项目新闻实时日志分析系统（视频+完整代码+文档免费下载）

ecshop二次开发 47个经典插件开发案例 讲解很详细

《《java基础入门（第二版）》练习题库（全）1》试卷.doc

精通CFD工程仿真与案例实战

《《java基础入门（第二版）》练习题库（全）2》试卷.doc

ecshop二次开发 47个经典插件开发案例 ecshop

DIV+CSS网站布局从入门到精通源代码

最新资源

动态规划的列子　几个案例

《绝了!Excel可以这样用:数据分析经典案例实战图表书》高宏著

ecshop二次开发 47个经典插件开发案例讲解很详细学习参考感谢提供者

ecshop二次开发 47个经典插件开发案例讲解很详细