D. 数字三角形

传统题

1000ms

512MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

下图显示了一个数字三角形。每一步都可以向左斜下方走或向右斜下方走，计算从顶到底某条路线上经过的数字的最大和。

在上面的样例中，从 7→3→8→7→5 的路径产生了最大权值。

第 $1$ 行包含一个整数 $n$ ，表示三角形的行数。下面的 $n$ 行描述了三角形的数据。三角形中的所有整数都为 $0$ ～ $9$ $9$ 。

输出从顶到底某条路线上经过的数字的最大和。

$1<n≤100$