问题 26299 --【递推】数字三角形(例题)

26299: 【递推】数字三角形(例题)

时间限制: 1 Sec  内存限制: 128 MB
提交: 37  解决: 31
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][44kb]

题目描述


【例3.1数字三角形。如下所示为一个数字三角形。请编一个程序计算从顶到底的某处的一条路径,使该路径所经过的数字总和最大。只要求输出总和。

                                    

    1、 一步可沿左斜线向下或右斜线向下走;

    2、 三角形行数小于等于100;

    3、 三角形中的数字为0,1,…,99;

    测试数据通过键盘逐行输入,如上例数据应以如下所示格式输入:

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

输入

    第一行,正整数n,表示数字三角形的行数,n100;

    接下来共n行,第i行(1in)有i个正整数,所有整数介于0~99之间。

输出

    最大的数字和。

样例输入

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

样例输出

30

提示

来源

[提交][状态]