首页 > 编程语言 > 详细

算法第三章上机实践报告

时间:2019-10-22 00:13:43      阅读:72      评论:0      收藏:0      [点我收藏+]

 

  1. 实践题目

  给定一个由 n行数字组成的数字三角形如下图所示。试设计一个算法,计算出从三角形 的顶至底的一条路径(每一步可沿左斜线向下或右斜线向下),使该路径经过的数字总和最大。

 

 

  1. 问题描述

创建两个数组,一个数组用于存放数字三角形,一个用于存放从底端开始到达某个元素的最大路径(只创建一个数组也是可以的,然后将结果不断覆盖)。

使用动态规划和便签本的方式来解决这个问题。

 

  1. 算法描述

递归方程式

m[i][j] = m[i][j]    i = n-1

       0 <= j <= i

       max(m[i+1][j], m[i+1][j+1]) + t[i][j]    i < n-1

 

  1. 算法时间空间负责度分析

     该算法时间空间复杂度都是On2

 

  1. 心得体会

    动态规划并不是我擅长的部分,尤其是第三题,所以还有很多需要继续学习和进步的地方。

算法第三章上机实践报告

原文:https://www.cnblogs.com/jumaodangdawang/p/11717143.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!