3208 - 数字三角形问题

给定n行数字组成的数字三角形,需要从顶走到底层。试设计一个算法,找到从顶走到底的路径,且该路径经过的数字总和最大。 例

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

最优路径是7-3-8-7-5,和为30

输入

第一行为一个数字n。 接着有n行,为数字三角形各行的数字。

输出

最大路径数字值

样例

输入

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

输出

30

来源

动规专题

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题