#O1036. 数字三角形

数字三角形

题目描述

给定一个 nn 行的数字三角形,从顶部的数出发,每次只能向左下或右下移动一格,一直走到底部,求路径上数字之和的最大值。

题目类型

动态规划

输入格式

第一行一个整数 nn。

接下来 nn 行,第 ii 行有 ii 个整数。

输出格式

一行一个整数,表示最大路径和。

样例 #1

样例输入 #1

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

样例输出 #1

30

数据规模与约定

数据范围 说明
1≤n≤10001 \le n \le 1000 行数
−109≤ai,j≤109-10^9 \le a_{i,j} \le 10^9 数字
  • 结果可能超过 int,请使用 long long。