问题2118--数字三角形Ⅳ

2118: 数字三角形Ⅳ

时间限制: 1 Sec  内存限制: 128 MB
提交: 9  解决: 7
[提交] [状态] [讨论版] [命题人:]

题目描述

下图显示了一个数字三角形。每一步都可以向左斜下方走或向右斜下方走，计算从顶到底某条路线上经过的数字的最大和。


输入

第1行包含一个整数n （1<n ≤100），表示三角形的行数。下面的n 行描述了三角形的数据。三角形中的所有整数都为0～99。

输出

输出从顶到底某条路线上经过的数字的最大和。

样例输入 Copy 

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

样例输出 Copy 

30

来源/分类

动态规划算法 线性DP 
[提交] [状态]