描述

7
3   8
8   1   0
2   7   4   4
4   5   2   6   5
(Figure 1)

输入

程序从标准输入读取数据：

• 第1行：整数$N$，表示三角形的行数（$1 < N \leq 100$）；
• 接下来的$N$行：描述三角形的数据，每行包含若干整数（范围$0$到$99$），用空格分隔。

输出

程序向标准输出写入：

• 第1行：路径数字之和的最大值（整数）。

示例

输入数据1

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

输出数据1

30

来源
IOI 1994

补充说明

• 动态规划解法：典型的数字三角形问题，可通过自底向上的动态规划高效求解。
• 状态转移方程：
  设$dp[i][j]$表示从第$i$行第$j$列出发到底部的最大路径和，则：$$dp[i][j] = triangle[i][j] + \max(dp[i+1][j], dp[i+1][j+1]) $$
• 边界条件：最底层$dp[N][j] = triangle[N][j]$。