3553: 数字三角形路径和最大值

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:11 解决:10

题目描述

给定一个数字三角形,从顶部到底部的一条路径,每一步只能走到相邻的下方节点。求所有路径中数字总和的最大值。

            2

        3      4

     6     5      7

4      1     8       3

例如:最大路径为 8 → 7 → 4 → 2,总和是 21

输入

第一行一个整数 n,表示三角形的层数。 接下来 n 行,第 i 行有 i 个整数,表示第 i 层的数字。

输出

一行一个整数,表示路径数字总和的最大值。

样例输入 复制

4
2
3 4
6 5 7
4 1 8 3

样例输出 复制

21

提示

n<100