Problem : Number Pyramid / 数塔

版权信息： 本题考察动态规划算法的应用，主要是通过从底层向上层遍历来计算最大路径和。

---

任务总览

任务名称	时间限制	内存限制	分数
数塔	1 sec	1024 MB	10 points

---

题目描述

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

例如，给定一个数塔：

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

要求从底层走到顶层，经过的数字的最大和是多少？

---

输入格式

输入数据首先包括一个整数N (1 ≤ N ≤ 100)，表示数塔的高度，接下来用N行数字表示数塔，其中第i行有i个整数，且所有的整数均在区间[0,99]内。

---

输出格式

输出一个整数，表示从底层走到顶层经过的数字的最大和。

---

输入输出示例

输入示例 1

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

输出示例 1

30

解释：

从底到顶的最大路径是：

7 → 8 → 8 → 7 → 5

路径和为 30。

---

解题思路

本题可以用动态规划来求解。我们可以从数塔的底层开始，逐步向上层更新每个节点的最大路径和。

• 设 dp[i][j] 表示到达数塔中第i行第j个数字的最大路径和。
• 初始时，dp 数组的最后一行即为数塔的最后一行。
• 然后逐行计算，从倒数第二行开始，每个节点的最大路径和等于当前节点的值加上它下面两个相邻节点的最大路径和。
• 最终，dp[0][0] 就是从底层到顶层的最大路径和。

---

时间复杂度分析

步骤	复杂度
读取输入数据	O(N^2)
动态规划计算
总复杂度	O(N^2)

本题的时间复杂度是O(N^2)，其中N是数塔的高度。由于数塔的每一层的元素数目是逐层递增的，所以计算复杂度是O(N^2)，适用于最大输入限制。

---

结论

本题通过动态规划有效地计算了从底层到顶层的最大路径和。