数字三角形最佳路径问题

图 1 给出了一个数字三角形。 从三角形的顶部

到底部有很多条不同的路径。 对于每条路径， 把路径上面的数加起来可以得到一个和，
你的任务就是找到最大的和。 注意： 路径上的每一步只能从一个数走到下一层上和它
最近的左边的那个数或者右边的那个数。
输入： 输入的是一行是一个整数 N (1 N = 100)， 给出三角形的行数。 下面的 N 行
给出数字三角形。 数字三角形上的数的范围都在 0 和 100 之间。
输出： 输出最大的和。
样例输入
5 7 3
8
8 1 0
2 7 4 4
4 5 2 6 5
样例输出
30