4228 - 基础算法-递推算法:数字三角升级版

通过次数

22

提交次数

90

时间限制 : 1 秒
内存限制 : 128 MB

在如下的数字三角形中寻找一个从右下角到第一列的路径,对于任意一个点(第一列除外),每一步只可以向左或者向左上走,找一条经过的数字之和最大的路径,求出这个和。

15664455594331.png

输入

5 //代表有5行

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

输出

30

样例

输入

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

输出

30