算法竞赛（蓝桥杯）贪心算法1——数塔问题
题目描述
有如下所示的数塔，要求从底层走到顶层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？
输入
输入数据首先包括一个整数整数 N (1≤N≤100)，表示数塔的高度，接下来用 N 行数字表示数塔，其中第i 行有个i 个整数，且所有的整数均在区间 [0,99] 内。
输出
从底层走到顶层经过的数字的最大和是多少？
样例
输入
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5输出
30
题解
1. 导入必要的模块
没有导入任何模块，因为它使用了标准的输入输出函数
input()和print()。2. 读取输入数据
Python复制
n = int(input())这行代码读取一个整数
n，表示数字三角形的行数。3. 初始化数字三角形
Python复制
a = [] for i in range(n): a.append(list(map(int, input().split())))这段代码读取
n行输入，每行包含若干个整数，构成数字三角形。这些整数被存储在一个二维列表a中。4. 动态规划求解最大路径和
Python复制
for i in range(n-2, -1, -1): for j in range(i + 1): # 确保遍历第i行的i+1个元素 a[i][j] = max(a[i][j] + a[i+1][j], a[i][j] + a[i+1][j+1])这段代码是动态规划的核心部分。它从倒数第二行开始，自底向上更新每一行的元素值。具体步骤如下：
外层循环：
for i in range(n-2, -1, -1)从倒数第二行开始，逐行向上遍历，直到第一行。内层循环：
for j in range(i + 1)遍历当前行的每个元素。第i行有i + 1个元素。更新元素值：
a[i][j] = max(a[i][j] + a[i+1][j], a[i][j] + a[i+1][j+1])将当前元素a[i][j]与下一行的两个相邻元素a[i+1][j]和a[i+1][j+1]中的较大值相加，更新a[i][j]。5. 输出结果
Python复制
print(a[0][0])最后，输出数字三角形顶部的元素
a[0][0]，它包含了从顶部到底部的最大路径和。示例
假设输入如下：
复制
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
n = 5表示数字三角形有5行。数字三角形如下：
复制
7 3 8 8 1 0 2 7 4 4 4 5 2 6 5按照动态规划的步骤，我们从倒数第二行开始计算：
第4行（倒数第二行）：
a[3][0] = 2 + max(4, 5) = 2 + 5 = 7
a[3][1] = 7 + max(5, 2) = 7 + 5 = 12
a[3][2] = 4 + max(2, 6) = 4 + 6 = 10
a[3][3] = 4 + max(6, 5) = 4 + 6 = 10第3行：
a[2][0] = 8 + max(7, 12) = 8 + 12 = 20
a[2][1] = 1 + max(12, 10) = 1 + 12 = 13
a[2][2] = 0 + max(10, 10) = 0 + 10 = 10第2行：
a[1][0] = 3 + max(20, 13) = 3 + 20 = 23
a[1][1] = 8 + max(13, 10) = 8 + 13 = 21第1行：
a[0][0] = 7 + max(23, 21) = 7 + 23 = 30最终，
a[0][0]的值为 30，表示从顶部到底部的最大路径和为 30。总结
通过自底向上的动态规划方法，我们可以高效地求解数字三角形的最大路径和。这种方法的时间复杂度为 O(n^2)，适用于处理较大规模的数字三角形。希望这篇文章能帮助你更好地理解这段代码的工作原理和实现细节。
完整代码
a=[] for i in range(n): a.append(list(map(int,input().split()))) for i in range(n-2,-1,-1): for j in range(i+1):# 确保遍历第j行有i个元素,因为range(0)无法进入循环 a[i][j]=max(a[i][j]+a[i+1][j],a[i][j]+a[i+1][j+1]) print(a[0][0])
原文地址：https://blog.csdn.net/m0_73581472/article/details/145169663
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！