例 1：数字三角形

如下所示为一个数字三角形。请编写一个程序，计算从顶到底的一条路径，使该路径上经过的数字之和最大。只需输出这个最大总和。

要求：

1. 每一步可以沿左下对角线或右下对角线移动；
2. 三角形的行数不超过 100；
3. 三角形中的数字取值范围为 0、1、……、99。

测试数据通过键盘逐行输入。对于上面的示例，输入格式如下：

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

**算法分析**

该问题有多种解法。可以从动态规划的思想出发，考虑如下思路：

当从顶层沿某一路径走到第 *i* 层，并继续向第 *i + 1* 层前进时，选择一定是在其下方两条可行路径中，使结果最大的那个方向。因此，可以采用自底向上的方法进行求解。

设 `a[i][j]` 表示从位置 `(i, j)` 出发到达第 `n` 层所能获得的最大路径和，则有：

a[i][j] = max(a[i][j] + a[i+1][j], a[i][j] + a[i+1][j+1])

其中，`a[1][1]` 即为所求的最大数字总和。