3666: 数字三角形问题,《算法入门经典》P259,动态规划,刘丽萍,CCF六级
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:1146
解决:376
题目描述
下图给出了一个数字三角形,请编写一个程序,计算从顶至底的某处的一条路径,使该路径所经过的数字的总和最大。
(1)每一步可沿左斜线向下或右斜线向下
(2)1 < 三角形行数 < 100
(3)三角形数字为0,1,…99
(1)每一步可沿左斜线向下或右斜线向下
(2)1 < 三角形行数 < 100
(3)三角形数字为0,1,…99
输入
有很多个测试案例,对于每一个测试案例, 通过键盘逐行输入,第1行是输入整数(如果该整数是0,就表示结束,不需要再处理),表示三角形行数n,然后是n行数
输出
输出最大值。
样例输入 复制
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
样例输出 复制
30