Статья Автор: Рабаданова Алина

правый нижний

n, m = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]
dp = [[0] * m for i in range(n)]
dp[n-1][m-1] = a[n-1][m-1]

for i in range(n-2, -1, -1):
    dp[i][m-1] = dp[i+1][m-1] + a[i][m-1]

for i in range(m-2, -1, -1):
    dp[n-1][i] = dp[n-1][i+1] + a[n-1][i]

for i in range(n-2, -1, -1):
    for j in range(m-2, -1, -1):
        dp[i][j] = max(dp[i+1][j], dp[i][j+1]) + a[i][j]

print(dp[0][0])

Чтобы оставить комментарий нужна авторизация

Печать