hzCPPOJ

P1044 数字三角形

时间限制:  0 s      内存限制:   128 MB
提交:31     正确:25     分值:97

题目描述

给定一个共有n行的三角形矩阵A,其中第i行有i列。从左上角出发,每次可以向下方或者右下方走一步,最终到达底部。请编一个程序计算从顶至底的某处的一条路径,使该路径所经过的数字的总和最大

1< 三角形行数< 25;  三角形中的数字为整数< 1000;

输入

第一行为N,表示有N行 

之后的第N+1行,有N个用空格间隔的整数

输出

路径所经过的数字的总和最大的答案

样例

样例输入:
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
样例输出:
30

提示

搜索80分,记忆化搜索AC

来源/分类