Гарри — почтальон. У него есть почтовый участок размером n * m (матричный / 2D-список). Каждый слот в 2D-списке представляет количество писем в этом месте.
Гарри может идти только вправо и вниз. Он начинает обход в (0, 0) и заканчивает в (n-1, m-1). n представляет высоту, а m — длину матрицы.
Письма Гарри может брать только там, где находится.
Напишите функцию, возвращающую максимальное количество писем, которое Гарри может подобрать.
Примечание. Если матрица пуста, верните -1.
def harry(po):
n, m = len(po), len(po[0])
if n == 0 or m == 0:
return -1
if n == 1 and m == 1:
return po[0][0]
for c in range(1, m):
po[0][c] += po[0][c-1]
for r in range(1, n):
po[r][0] += po[r-1][0]
for r in range(1, n):
for c in range(1, m):
po[r][c] += max(po[r-1][c], po[r][c-1])
return po[-1][-1]
