‹ 上一题 下一题 ›

07382. 三角形最小路径 未做

1000 ms 256 MB 测试点 10 通过率 100% 线性DP

题目描述

一个 行的数塔,第 行有 个数。从塔顶走到塔底,每步走到下一行相邻的两个数之一(下方或右下),路径上数字全部累加。最小总和是多少?

输入格式

第一行一个整数 。
接下来 行,第 行 个整数。

输出格式

一行一个整数:最小路径和。

样例

输入
4
2
3 4
6 5 7
4 1 8 3
输出
11

数据范围

,。

输入
输出

            
答案