当前位置：首页 > article >正文

算法竞赛（蓝桥杯）贪心算法1——数塔问题

article 2025/1/16 9:27:07

题目描述

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

输入

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

输出

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

样例

输入

输出

题解

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])