刷题刷出新高度，偷偷领先！偷偷领先！偷偷领先！ 关注我们，悄悄成为最优秀的自己！

简答题

提示信息:

数字塔是由 N 行数堆积而成，最顶层只有一个数，次顶层两个数，以此类推。

相邻层之间的数用线连接，下一层的每个数与它上一层左上方和右上方的数连接 (左上方或右上方没有数则不需要连接)。

编程实现:

有一个 N 行 (0≤N≤50) 的数字塔，小蓝想要从最顶层开始，沿着线层一层向下移动，移动到最底层。小蓝想找出一条移动路径，使得路径上的数之和最大 (包含顶层和底层的数)，请计算出最大的和是多少。 

例如: N=5，5 层的数字塔，每层的数如下图所示: 

从顶层数为 2 到底层数为 15 的路径上的数之和最大，最大和为 48。路径为: 

2+3-18-10- 15。 

输入描述

第一行输入一个正整数 N (2<N<50) ，表示数字塔的层数接下来输入 N 行，其中第一行为一个正整数，接下来每行的正整数比上一行多一个，每行的正整数之间以一个英文逗号隔开 (1<1 整数<1000) 

输出描述

输出一个整数，表示从数字塔最顶层移动到最底层的路径上的数之和的最大值 


【输入样例】 

5
2
3,12
18,8,3
5,10,13,2
4,15,7,6,8

【输出样例

48

使用微信搜索喵呜刷题，轻松应对考试！

答案：

```pythondef max_sum(n):nums = []for i in range(n):nums.append(list(map(int, input().split(','))))dp = [[0] * (len(nums[i]) + 1) for _ in range(n)]for i in range(n):for j in range(1, len(nums[i]) + 1):dp[i][j] = max(dp[i - 1][j - 1] + nums[i][j - 1], dp[i - 1][j])return dp[n - 1][len(nums[n - 1])]n = int(input())print(max_sum(n))```

解析：

【喵呜刷题小喵解析】：
本题是一个动态规划问题，可以通过定义dp数组来解决。

首先，我们定义一个二维数组dp，其中dp[i][j]表示从顶层到第i层，且选取第i层的前j个数的最大和。

然后，我们遍历每一层，对于每一层，我们遍历其每一个数，选择取这个数或者不取这个数，然后更新dp数组。

最后，返回dp[n-1][len(nums[n-1])]即可，其中n是数字塔的层数，nums[n-1]是最后一层的数的列表。

需要注意的是，如果某一层只有一个数，我们只需要更新dp[i][1]，不需要更新dp[i][0]。因为题目要求路径上的数之和最大，如果某一层只有一个数，那么我们必须选取这个数，所以dp[i][0]的值就是dp[i-1][0]。

以上代码的时间复杂度为O(n^2)，其中n是数字塔的层数，满足题目要求的时间复杂度。
创作类型：
原创

本文链接：提示信息: 数字塔是由 N 行数堆积而成，最顶层只有一个数，次顶层两个数，以此类推。 相邻层之间的数

版权声明：本站点所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速，微信扫码，获取考试解析、体验刷题服务，开启你的学习加速器！

分享考题
share