Problem1481--数字三角形

1481: 数字三角形

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Solved: 6Submit: 9Statistics

Description

数字三角形，从三角形顶部往下走，只能往左下或右下走，求走到最下面时所经过的数字和最大为多少？（下图为n=6时的情况)







2








96
30






83
52
60




21
65
44
61


8
79
50
41
21
61
41
50
38
79
10

Input

第1行：整数n(1<=n<=1000)
第2-n+1行：每行若干整数，第i行有i-1个整数，空格分隔。

Output

一行：一个整数，表示所经过数字的最大和。

Sample Input Copy 

6					
2					
96	30				
83	52	60			
21	65	44	61		
8	79	50	41	21	
61	41	50	38	79	10

Sample Output Copy 

375

Source/Category

动态规划 
SubmitWeb Board