数字三角形问题

题目描述

给定n行数字组成的数字三角形，需要从顶走到底层。试设计一个算法，找到从顶走到底的路径，且该路径经过的数字总和最大。 例

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

最优路径是7-3-8-7-5，和为30

输入

第一行为一个数字n。 接着有n行，为数字三角形各行的数字。

输出

最大路径数字值

样例

来源

动规专题