Python3_数字三角形
作者:
成理第一深情
,
2024-02-06 13:50:01
,
所有人可见
,
阅读 41
"""
动态规划思路:
状态表示:
集合:f[i][j]:表示从起点开始到[i, j]这个点的所有路径
属性:最大值
状态计算:
f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j])
"""
n = int(input())
a = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
a[i][1:] = map(int, input().strip().split())
# print(a)
f = [[-float("inf")] * (n + 1) for _ in range(n + 1)]
f[1][1] = a[1][1]
for i in range(2, n + 1):
for j in range(1, i + 1):
f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j])
print(max(f[n]))