Решение задачи #3 на Python с Яндекс CodeRun — Вывести маршрут максимальной стоимости

Вариант решения задачи на языке программирования Python с Яндекс CodeRun.
Название задачи: Вывести маршрут максимальной стоимости.
Сложность: Средняя.
Статус решения: "Решено".

Условие задачи:
В левом верхнем углу прямоугольной таблицы размером N×MN×M находится черепашка. В каждой клетке таблицы записано некоторое число. Черепашка может перемещаться вправо или вниз, при этом маршрут черепашки заканчивается в правом нижнем углу таблицы.

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

Формат ввода:
В первой строке входных данных записаны два натуральных числа N и M, не превосходящих 100 — размеры таблицы. Далее идет N строк, каждая из которых содержит M чисел, разделенных пробелами — описание таблицы. Все числа в клетках таблицы целые и могут принимать значения от 0 до 100.

Формат вывода:
Первая строка выходных данных содержит максимальную возможную сумму, вторая — маршрут, на котором достигается эта сумма. Маршрут выводится в виде последовательности, которая должна содержать N-1 букву D, означающую передвижение вниз и M-1 букву R, означающую передвижение направо. Если таких последовательностей несколько, необходимо вывести ровно одну (любую) из них.

Python

def max_turtle_path(n, m, grid):
    # Создаем массив для хранения максимальных сумм для каждой клетки
    dp = [[0] * m for _ in range(n)]
    # Создаем массив для хранения пути до каждой клетки
    path = [[None] * m for _ in range(n)]

    # Инициализируем первую клетку
    dp[0][0] = grid[0][0]

    # Заполняем первую строку (только вправо)
    for j in range(1, m):
        dp[0][j] = dp[0][j - 1] + grid[0][j]
        path[0][j] = 'R'

    # Заполняем первый столбец (только вниз)
    for i in range(1, n):
        dp[i][0] = dp[i - 1][0] + grid[i][0]
        path[i][0] = 'D'

    # Заполняем остальные клетки
    for i in range(1, n):
        for j in range(1, m):
            if dp[i - 1][j] > dp[i][j - 1]:  # Сравниваем путь сверху и слева
                dp[i][j] = dp[i - 1][j] + grid[i][j]
                path[i][j] = 'D'  # Движение вниз
            else:
                dp[i][j] = dp[i][j - 1] + grid[i][j]
                path[i][j] = 'R'  # Движение вправо

    # Восстанавливаем маршрут из path
    route = []
    i, j = n - 1, m - 1
    while i > 0 or j > 0:
        route.append(path[i][j])
        if path[i][j] == 'D':
            i -= 1
        else:  # path[i][j] == 'R'
            j -= 1

    route.reverse()  # Переворачиваем, чтобы маршрут шел от начала к концу

    # Возвращаем максимальную сумму и маршрут
    return dp[n - 1][m - 1], ''.join(route)


# Чтение входных данных
n, m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]

# Получение результата
max_sum, route = max_turtle_path(n, m, grid)

# Вывод результата
print(max_sum)
print(route)

Объяснение кода

Входные данные:
Размеры таблицы (n, m) и сама таблица (grid) считываются из входных данных.

Динамическое программирование (DP):
Мы создаем массив dp, где dp[i][j] хранит максимальную сумму, которую можно получить, достигнув клетки (i, j).

Инициализация:
Первая клетка таблицы — это начальная позиция, её значение просто копируем в dp[0][0].
Первая строка заполняется последовательным движением вправо.
Первый столбец заполняется последовательным движением вниз.

Заполнение таблицы DP:
Для каждой клетки (i, j) выбираем максимальную сумму из двух возможных направлений: сверху (dp[i-1][j]) или слева (dp[i][j-1]), добавляя значение текущей клетки (grid[i][j]).

Восстановление пути:
Сохраняем путь до каждой клетки в массиве path.
Для восстановления маршрута начинаем с правого нижнего угла и идем к верхнему левому, используя информацию в path.

Результат:
Максимальная сумма находится в dp[n-1][m-1].
Маршрут восстанавливается из массива path и выводится в виде строки.

Источник решения: hdhAI.com