408. 数字三角形
时间限制：1000 MS 内存限制：128 MB
题目描述
# 数字三角形 ## 题目描述 给定一个有 $n$ 层的数字三角形，第 $i$ 层有 $i$ 个结点，每个结点上都有一个整数。 从顶部的结点出发，每次可以移动到当前结点左下方或右下方的结点，直到到达底层。具体来说，从第 $i$ 层的第 $j$ 个结点，只能移动到第 $i+1$ 层的第 $j$ 个结点或第 $j+1$ 个结点。 请找出一条从顶部到底层的路径，使路径上所有结点的数字之和最大。路径必须包含每层恰好一个结点。 ## 输入格式 从文件 `triangle.in` 中读入数据。 第一行包含一个整数 $n$，表示数字三角形的层数。 接下来 $n$ 行，第 $i$ 行包含 $i$ 个整数，按从左到右的顺序表示第 $i$ 层各结点的值。 ## 输出格式 输出到文件 `triangle.out`。 输出一个整数，表示从顶部到底层的最大路径数字和。 ## 数据范围 - $1 \le n \le 500$。 - 每个结点的值均为整数，且在 $[-10000, 10000]$ 内。 ## 样例输入 ``` 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 ``` ## 样例输出 ``` 30 ``` ## 样例说明 选择路径上的数字依次为 $7, 3, 8, 7, 5$，其和为 $30$，这是最大的路径数字和。 ## 时间与空间限制 - 时间限制：$1000$ 毫秒。 - 空间限制：$128$ MB。