#O1036. 数字三角形
数字三角形
题目描述
给定一个 行的数字三角形,从顶部的数出发,每次只能向左下或右下移动一格,一直走到底部,求路径上数字之和的最大值。
题目类型
动态规划
输入格式
第一行一个整数 。
接下来 行,第 行有 个整数。
输出格式
一行一个整数,表示最大路径和。
样例 #1
样例输入 #1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
样例输出 #1
30
数据规模与约定
| 数据范围 | 说明 |
|---|---|
| 行数 | |
| 数字 |
- 结果可能超过
int,请使用long long。