Какое максимальное значение суммы чисел через которые проползла черепашка может быть достигнуто в прямоугольной таблице

Задание: Какое максимальное значение суммы чисел через которые проползла черепашка может быть достигнуто в прямоугольной таблице размером n×m? Какому маршруту будет соответствовать максимальное значение суммы?

Объяснение: Чтобы найти максимальную сумму чисел, через которые проползла черепашка в прямоугольной таблице размером n×m, мы можем использовать метод динамического программирования. Для этого создадим новую матрицу размером n×m, где каждая ячейка будет содержать максимальную сумму чисел, которые черепашка могла пройти до этой ячейки.

Начнем с правой нижней ячейки (n, m). Мы можем просто записать значение этой ячейки в новую матрицу, так как это будет единственный путь, который черепашка может пройти, чтобы добраться до конца.

Затем работаем с остальными ячейками. Для каждой ячейки (i, j), где i < n и j < m, находим максимальное значение суммы, которое черепашка может достичь, двигаясь только вправо или вниз. Это можно сделать с помощью формулы:

Максимальная сумма в ячейке (i, j) = Значение в ячейке (i, j) + максимальное из (Максимальная сумма в ячейке (i-1, j), Максимальная сумма в ячейке (i, j-1)).

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

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

Пример:

Входные данные: n = 3, m = 4

Таблица чисел:

1 2 3 4
5 6 7 8
9 10 11 12

Выходные данные:
Максимальное значение суммы: 36

Маршрут: (1, 1) -> (2, 1) -> (3, 1) -> (3, 2) -> (3, 3) -> (3, 4)

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

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