#1259. 数塔问题

数塔问题

题目描述

在讲述DP算法的时候,一个经典的例子就是数塔问题,它是这样描述的:

有如下所示的数塔,要求从顶层走到底层,若每一步只能走到相邻的结点,则经过的结点的数字之和最大是多少?

已经告诉你了,这是个DP的题目,你能AC吗?(图见课件上练习题的示图)

输入格式

第一行n(n<10)\red{n(n<10)},表示数塔的层数 从第2行n+1\red{n+1}行,每行有若干个数据,表示数塔中的数值。

输出格式

输出路径和最大的路径值。

样例

输入样例

5
13
11  8
12  7  26
6  14  15  8
12  7  13  24  11

输出样例

86

统计

相关

在下列比赛中:

Day1