最佳寻宝路径

题目描述

一个由不同价值的金币构成的三角形宝藏堆，每个金币的价值都用正整数来表示。如下所示的宝藏堆结构（假设目前有5层宝藏）： 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 一个贪婪的冒险家从宝藏堆的顶部开始，沿着宝藏堆向下寻找金币，直到找到最后一层。他每次只能选择向下走到正下方的金币或者右下方的金币。他的目标是找到一条路径，使得这条路径上所有金币的总价值最大，这就是最佳寻宝路径。你的任务就是帮助这个贪婪的冒险家计算出最佳寻宝路径上金币的总价值。

输入格式

第一行，整数n，代表三角形层数。（1≤n≤100） 接下来n行，每行若干整数，第i行包含i-1个整数，整数之间使用空格分隔。（0≤整数≤2000）

输出格式

一行，一个整数，最佳寻宝路径上金币的总价值。

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

30

提示

（暂无提示）

来源

童程童美