ID: 566

传统题

1000ms

128MiB

难度: (无)

上传者:

标签>

基础练习-数组

洛谷

动态规划

贪心

数论

递归

数字三角形

题目描述

给定一个具有N层的数学三角形如下图，从顶至底有多条路径，每一步可沿左斜线向下或沿右斜线向下，路径所经过的数字之和为路径得分，请求出最小路径得分。

2

6 2

1 8 4

1 5 6 8

输入说明

第1行，一个正整数n，表示三角形的行数

第2至n+1行，照描述输入三角形

输出说明

最小路径得分，行末有换行

样例

输入

输出