def find_max_sum(triangle):
rows = len(triangle)
# 创建一个二维数组,用于保存每个位置的最大路径和
dp = [[0] * (i + 1) for i in range(rows)]
# 将最后一行的值赋给dp数组最后一行
dp[rows-1] = triangle[rows-1]
# 从倒数第二行开始向上计算最大路径和
for i in range(rows-2, -1, -1):
for j in range(i+1):
# 当前位置的最大路径和等于下一行相邻两个位置的较大值加上当前位置的值
dp[i][j] = triangle[i][j] + max(dp[i+1][j], dp[i+1][j+1])
# 最大路径和即为dp数组的第一个元素
return dp[0][0]
# 读取输入数据
triangle = []
input_data = '''\
8
9, 2, 1
3, 8, 5, 5
5, 6, 3, 7, 6
3, 8, 5, 5
9, 2, 1
4, 9
8
'''
lines = input_data.strip().split('\n')
for line in lines:
row = list(map(int, line.split(',')))
triangle.append(row)
# 调用函数计算最大路径和
max_sum = find_max_sum(triangle)
# 输出结果
print("最大值路径之和是:", max_sum)
rows = len(triangle)
# 创建一个二维数组,用于保存每个位置的最大路径和
dp = [[0] * (i + 1) for i in range(rows)]
# 将最后一行的值赋给dp数组最后一行
dp[rows-1] = triangle[rows-1]
# 从倒数第二行开始向上计算最大路径和
for i in range(rows-2, -1, -1):
for j in range(i+1):
# 当前位置的最大路径和等于下一行相邻两个位置的较大值加上当前位置的值
dp[i][j] = triangle[i][j] + max(dp[i+1][j], dp[i+1][j+1])
# 最大路径和即为dp数组的第一个元素
return dp[0][0]
# 读取输入数据
triangle = []
input_data = '''\
8
9, 2, 1
3, 8, 5, 5
5, 6, 3, 7, 6
3, 8, 5, 5
9, 2, 1
4, 9
8
'''
lines = input_data.strip().split('\n')
for line in lines:
row = list(map(int, line.split(',')))
triangle.append(row)
# 调用函数计算最大路径和
max_sum = find_max_sum(triangle)
# 输出结果
print("最大值路径之和是:", max_sum)