Найдите маршрут с максимальной стоимостью в левом верхнем углу прямоугольной таблицы размером N×M, где у каждой клетки

Тема вопроса: Задача о маршруте в таблице

Разъяснение:
Данная задача может быть решена с использованием динамического программирования. Мы можем создать таблицу размером N×M, в которой будем хранить сумму наибольшего маршрута до каждой клетки. Начальное значение в первой клетке будет равно числу в первой клетке исходной таблицы.

Затем мы начинаем обходить таблицу построчно, начиная с второй строки. Для каждой клетки мы смотрим на клетку выше и на клетку слева, и берем максимальную сумму из этих двух клеток и текущей клетки. Таким образом, значение в каждой клетке таблицы будет равно сумме наибольшего маршрута до этой клетки.

После заполнения таблицы, наибольшая сумма будет находиться в правом нижнем углу таблицы. Маршрут можно восстановить, начиная с этой клетки и двигаясь по наибольшим значениям в клетках сверху и слева.

Пример:
Предположим, у нас есть следующая таблица размером 3×4:

1 2 3 4

5 6 7 8

9 10 11 12

Наибольшая сумма маршрута в этой таблице будет 1 + 2 + 6 + 7 + 11 + 12 = 39. Маршрут можно восстановить следующим образом: (1,1) -> (1,2) -> (2,2) -> (2,3) -> (3,3) -> (3,4).

Совет:
Для лучшего понимания решения задачи, можно нарисовать таблицу на бумаге и поэтапно заполнять значения, следуя описанному алгоритму. Также, примеры использования могут помочь визуализировать решение.

Задание для закрепления:
Рассмотрим таблицу размером 4×5:

1 2 3 4 5

6 7 8 9 10

11 12 13 14 15

16 17 18 19 20

Найдите наибольшую сумму маршрута и сам маршрут.