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

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

1. Создайте таблицу размером N × M для хранения чисел в каждой клетке и суммы на каждом шаге.

2. Заполните первую строку и первый столбец таблицы значениями из входных данных. Это означает, что мы заполняем значения каждой клетки построчно и слева направо.

3. Для каждой клетки (i, j), где i>0 и j>0, вычислите сумму значения клетки (i, j) и максимального значения между клеткой (i-1, j) и клеткой (i, j-1). Это означает, что мы выбираем между двумя предыдущими маршрутами: вправо или вниз, и выбираем путь с большей стоимостью.

4. Повторяйте шаг 3 для всех клеток таблицы, двигаясь слева направо и сверху вниз.

5. В конечной клетке (N, M) будет содержаться максимальная сумма чисел через клетки. Вы можете использовать эту сумму для получения наиболее выгодного маршрута.

6. Чтобы найти маршрут с наибольшей стоимостью, начните с конечной клетки и двигайтесь в обратном направлении, выбирая каждый раз путь с бОльшей стоимостью. Запишите координаты каждой посещенной клетки, чтобы получить маршрут.

Вот пример кода на языке Python, реализующий этот алгоритм:

python

def find_max_route(matrix):

    n = len(matrix)

    m = len(matrix[0])

    

    # Создание таблицы для хранения значений и сумм

    dp = [[0] * m for _ in range(n)]

    

    # Заполнение первой строки и первого столбца

    dp[0][0] = matrix[0][0]

    for i in range(1, n):

        dp[i][0] = dp[i-1][0] + matrix[i][0]

    for j in range(1, m):

        dp[0][j] = dp[0][j-1] + matrix[0][j]

    

    # Вычисление суммы для каждой клетки

    for i in range(1, n):

        for j in range(1, m):

            dp[i][j] = matrix[i][j] + max(dp[i-1][j], dp[i][j-1])

    

    # Восстановление маршрута

    route = []

    i, j = n-1, m-1

    while i > 0 or j > 0:

        route.append((i, j))

        if i == 0:

            j -= 1

        elif j == 0:

            i -= 1

        elif dp[i-1][j] > dp[i][j-1]:

            i -= 1

        else:

            j -= 1

    route.append((0, 0))

    

    route.reverse()

    

    return dp[n-1][m-1], route



# Пример использования

matrix = [

    [1, 2, 3],

    [4, 5, 6],

    [7, 8, 9]

]

max_sum, max_route = find_max_route(matrix)



print("Максимальная сумма чисел:", max_sum)

print("Маршрут:", max_route)

В этом примере у нас есть таблица 3x3, и черепашка может перемещаться только вниз или вправо. Максимальная сумма чисел через маршрут составляет 25, а маршрут проходит через клетки (0, 0), (1, 0), (2, 0), (2, 1), (2, 2).