Boss：数字三角形

编程闯关　难度 3

本星球大 Boss！从三角形顶端往下走，每步只能走左下或右下，求路上数字之和的最大值。提示：从底往上递推最好写！

题目描述

第一行输入整数 n（1 ≤ n ≤ 100）表示三角形行数。接下来 n 行，第 i 行有 i 个整数（0 ≤ 数字 ≤ 100）。从顶端出发，每步走到左下或右下的数字，求经过数字之和的最大值。

输入样例：
3
1
2 3
4 5 6

输出样例：
10

（路径 1→3→6）

知识点讲解

自底向上 DP：每个格子加上“它下面两个格子中较大的那个”，一路推到顶，a[1][1] 就是答案。