Pythonist

Кодинг-марафон. Задача № 6.

Гарри — почтальон. У него есть почтовый участок размером n * m (матричный / 2D-список). Каждый слот в 2D-списке представляет количество писем в этом месте.

Гарри может идти только вправо и вниз. Он начинает обход в (0, 0) и заканчивает в (n-1, m-1). n представляет высоту, а m — длину матрицы.

Письма Гарри может брать только там, где находится.

Напишите функцию, возвращающую максимальное количество писем, которое Гарри может подобрать.

Примеры

harry([[5, 2], [5, 2]]) ➞ 12
# (5+5+2)


harry([
  [1, 2, 3, 4, 5],
  [6, 7, 8, 9, 10],
  [11, 12, 13, 14, 15]
]) ➞ 72
# (1+6+11+12+13+14+15)


harry([[]]) ➞ -1

Примечание. Как вы видели в примере 3, если матрица пуста, верните -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]