Preparing NOJ

数字三角形问题

1000ms 65536K

Description:

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

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

Input:

输入的第1行是数字三角形的行数n1n100。接下来n行是数字三角形各行中的数字。所有数字在0..99之间。

Output:

输出到的第1行中的数是计算出的最大值。

Sample Input:

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

Sample Output:

30

Note:

undefined

本题由旧版NOJ导入,来源:算法设计与实验题解

Info

NOJ

Provider NOJ

Code NOJ1226

Tags

Submitted 9

Passed 6

AC Rate 66.67%

Date 04/20/2019 10:03:10

Related

Nothing Yet