问题 22500 -- 数字三角形 问题

22500: 数字三角形 问题

时间限制: 1 Sec  内存限制: 128 MB
提交: 16  解决: 13
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][84kb]

题目描述

给定一个由 n 行数字组成的数字三角形如下图所示。试设计一个算法,计算出从三角形

的顶至底的一条路径,使该路径经过的数字总和最大。


 


«编程任务:

对于给定的由 n 行数字组成的数字三角形,编程计算从三角形的顶至底的路径经过的数

字和的最大值。 

输入

1 行是数字三角形的行数 n1<=n<=100。接下

来 n 行是数字三角形各行中的数字。所有数字在 0..99 之间。 

输出

将计算结果输出,

第 1 行中的数是计算

出的最大值。 

样例输入

5 
7 
3 8 
8 1 0
2 7 4 4 
4 5 2 6 5 

样例输出

30

提示

来源

[提交][状态]