Home => ProblemSet => 1.8-04:数字三角形
Problem1316--1.8-04:数字三角形

1316: 1.8-04:数字三角形

Time Limit: 1 Sec  Memory Limit: 128 MB  Submit: 19  Solved: 36
[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]

Description

给定一个N层数字三角形，从顶至底有多条路径，每一步可沿左斜线向下或沿右斜线向下，路径所经过的数字之和为路径得分，请求出最大路径得分。 


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


Input

第一行，一个正整数n，表示三角形的行数(1<=n <= 100)；
第2至n+1行，照描述输入三角形，所有数字均为-100~100之间的整数

Output

最大路径得分，行末有换行

Sample Input Copy 

4
2
6 2
1 8 4
1 5 6 8

Sample Output Copy 

22

HINT

1<=n <= 100

Source/Category

递归 二维数组 动态规划 DFS 枚举 线性 
[ Submit ] [ Status ]