第十一届蓝桥杯：数字三角形

• 题目
• 暴力：最大路径和
• 题解：动态规划

题目

暴力：最大路径和

n = int(input())  # 输入数塔的行数
# 创建一个二维数组a来表示数塔，初始值都为0
a = [[0] * (n+1) for _ in range(n+1)]
# 从第1行开始逐行读取输入，并计算最大路径和
for i in range(1, n+1):
    for j in range(1, i+1):
        temp = int(input())  # 读取当前位置的值
        a[i][j] = max(a[i-1][j-1], a[i-1][j]) + temp  # 计算当前位置的最大路径和
res = 0
# 遍历最后一行，找到最大路径和
for i in range(1, n+1):
    if res < a[n][i]:
        res = a[n][i]
print(res)  # 输出最大路径和

题解：动态规划

n = int(input())  # 输入数塔的行数
dp = []  # 创建一个空列表 dp，i,j表示横纵坐标，dp的值表示在该坐标下的最大路径和
# 逐行读取输入，并将每行的值转换为整数列表，添加到 dp 列表中
for i in range(n):
    dp.append(list(map(int, input().split())))
# 从第2行开始计算最大路径和，可以防止下标溢出
for i in range(1, n):
    for j in range(i+1):
        if j == 0:  # 最左边一列的情况，只能来自于他的上一个
            dp[i][j] += dp[i-1][j]
        elif j == i:  # dp[i][j] 对角线的位置，只能来自他的左上
            dp[i][j] += dp[i-1][j-1]
        else:#其他情况的状态转移方程，当前位置的最大路径和等于上一级的正对元素和左上之间较大的一个路径和加上当前路径
            dp[i][j] += max(dp[i-1][j], dp[i-1][j-1])
#要保证向左下走的次数与向右下走的次数相差不能超过 1，那么如果最后一行是奇数个，就肯定落在最中心的点
# 如果是偶数，同理，只可能落在最中间的两点，取最后一行最中间两点的最大值
if n % 2 == 0:  # 偶数行数情况下取中间两点中的最大值
    print(max(dp[n-1][n//2-1], dp[n-1][n//2]))
else:
    print(dp[n-1][n//2])  # 奇数行数情况下取中间点