Description

（图３.１－１）示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路
径，使该路径所经过的数字的总和最大。
　●每一步可沿左斜线向下或右斜线向下走；
　●1＜三角形行数≤100；
　●三角形中的数字为整数0，1，…99；

　                              ７
　　　　　　　　　　　　　　　３　８
　　　　　　　　　　　　　　８　１　０
　　　　　　　　　　　　　２　７　４　４
　　　　　　　　　　　　４　５　２　６　５

　　　　　　　　　　　　　　　（图３.１－１）

Input Format

输入数据：
由INPUT.TXT文件中首先读到的是三角形的行数。
在例子中INPUT.TXT表示如下：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

Output Format

输出数据：
把最大总和（整数）写入OUTPUT.TXT文件。
上例为：
max=30
　　　　　　　　　　　　　　　

Source

基本算法-动态规划-动态规划与递推 一本通2018-第九章