1031: 22-数组-2-爬数塔
[Creator : ]
Description
小南在CSU的某个角落发现了一座由数字组成的斜塔，他I想到塔顶去看看。小南可以从底层任意一个数字出发逐层爬上去，每次可以爬至上一层数字上或者上一层左边相邻的数字上（第1列只能爬至正上方上一层的数字上）。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
如上图，小南如果从最下层也就是第5层的数字4向上爬，只能爬到上一层即第4层的2号数字上；如果从数字2爬，可以爬到其正上方的数字4上，也可以爬到数字7上；如果从最右边的数字5爬，则只能爬到其左上方的数字4上。
现在小南想知道，他从最下层开始爬到塔顶，如何选择爬上去的路径，使该路径经过的数字和最大？
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
如上图，小南如果从最下层也就是第5层的数字4向上爬，只能爬到上一层即第4层的2号数字上；如果从数字2爬，可以爬到其正上方的数字4上，也可以爬到数字7上；如果从最右边的数字5爬，则只能爬到其左上方的数字4上。
现在小南想知道，他从最下层开始爬到塔顶，如何选择爬上去的路径，使该路径经过的数字和最大？
Input
多组测试数据。
每组测试数据的第一行是一个整数n（1≤n≤100）表示数塔的高度，接下来用n行数字表示数塔，其中第i行有个i个整数，且所有的整数均在区间[0,99]内。
每组测试数据的第一行是一个整数n（1≤n≤100）表示数塔的高度，接下来用n行数字表示数塔，其中第i行有个i个整数，且所有的整数均在区间[0,99]内。
Output
对于每个组测试数据，输出一个整数表示得到的最大和，每个输出占一行。
Sample Input Copy
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Sample Output Copy
30