三角形谜题

题目描述

有一个数字组成的三角形，从三角形顶部往下走，只能往左下或右下走，求走到最下面时所经过的数字和最大为多少？

输入格式

第 $1$ 行：整数 $n$（$1 \le n \le 1000$）。第 $2$ 到 $n+1$ 行：每行若干整数，第 $i$ 行有 $i-1$ 个整数，空格分隔。

输出格式

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

样例输入 #1

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

样例输出 #1

30

数据范围

$1 \le n \le 1000$

知识点与难度

本题涉及的知识点从属于 GESP四级（递推、动态规划），难度等级：⭐⭐⭐⭐。

测试点分布