Задание 18: движение Робота по таблице (динамическое программирование)

Робот идёт по таблице только вправо и вниз — учимся искать самый «денежный» и самый «дешёвый» путь динамическим программированием.

Динамическое программирование (ДП) — метод, где ответ для клетки выражается через уже посчитанные ответы для соседних клеток.

Что проверяет задание 18

Задание 18 — базовый уровень, 1 балл, но на КЕГЭ его удобно решать кодом. Дана прямоугольная таблица чисел. Робот стартует в левой верхней клетке и идёт в правую нижнюю, на каждом шаге двигаясь только вправо или вниз. В клетках лежат монеты (или штрафы). Спрашивают максимальную и минимальную сумму, которую соберёт Робот за путь. К ЕГЭ часто прилагается файл с большой таблицей.

Теория: почему это динамика

В клетку (i, j) Робот может прийти только сверху (i−1, j) или слева (i, j−1) — больше ниоткуда, ведь он ходит вправо и вниз. Значит лучшая сумма до (i, j) — это значение клетки плюс лучшая из сумм до этих двух соседей. Заполняем таблицу dp сверху вниз и слева направо — к моменту обработки клетки её соседи уже посчитаны.

dp[i][j] = grid[i][j] + max(dp[i-1][j], dp[i][j-1])   # для максимума
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])   # для минимума

Для верхней строки соседа сверху нет, для левого столбца — слева; стартовая клетка равна себе.

Метод решения

Прочитайте таблицу в двумерный список.
Создайте таблицу dp того же размера.
Заполняйте dp по строкам слева направо: берите максимум (или минимум) из доступных соседей.
Ответ — в правой нижней клетке dp.

Решение на Python

grid = [
    [1, 3, 1, 5],
    [2, 1, 8, 1],
    [4, 2, 1, 6],
]
R, C = len(grid), len(grid[0])

def best_path(grid, use_max):
    R, C = len(grid), len(grid[0])
    dp = [[0] * C for _ in range(R)]
    for i in range(R):
        for j in range(C):
            if i == 0 and j == 0:
                dp[i][j] = grid[i][j]
                continue
            neighbors = []
            if i > 0:
                neighbors.append(dp[i - 1][j])   # сверху
            if j > 0:
                neighbors.append(dp[i][j - 1])   # слева
            chosen = max(neighbors) if use_max else min(neighbors)
            dp[i][j] = grid[i][j] + chosen
    return dp[R - 1][C - 1]

print("Максимальная сумма пути:", best_path(grid, use_max=True))
print("Минимальная сумма пути:", best_path(grid, use_max=False))

Вывод:

Максимальная сумма пути: 20
Минимальная сумма пути: 13

Проверим максимум вручную: путь 1→3→1→8→1→6 = 20 (вправо, вправо, вниз, вправо, вниз)… в любом случае ДП гарантированно находит оптимум, перебирать все пути не нужно — их экспоненциально много, а ДП работает за число клеток.

Чтение таблицы из «файла»

На экзамене таблицу читают из текстового файла. Принцип: каждая строка файла — строка таблицы, числа через пробел.

# На экзамене строки берут из файла: lines = f.readlines()
lines = ["1 3 1 5", "2 1 8 1", "4 2 1 6"]

grid = [[int(x) for x in line.split()] for line in lines]
R, C = len(grid), len(grid[0])
dp = [[0] * C for _ in range(R)]
for i in range(R):
    for j in range(C):
        if i == 0 and j == 0:
            dp[i][j] = grid[i][j]
        else:
            best = max(
                dp[i - 1][j] if i > 0 else -10**9,
                dp[i][j - 1] if j > 0 else -10**9,
            )
            dp[i][j] = grid[i][j] + best
print("Максимум:", dp[R - 1][C - 1])

Вывод:

Максимум: 20

Типичные ошибки

Перебирают все пути. Путей экспоненциально много; нужна именно динамика за O(строки·столбцы).
Неверно обрабатывают край. В верхней строке нет хода сверху, в левом столбце — слева; не берите несуществующего соседа.
Путают направление обхода. Заполнять надо так, чтобы соседи уже были посчитаны: сверху вниз, слева направо.
Считают только максимум. В задании 18 обычно просят и максимум, и минимум — два прогона.

Итог

Робот ходит вправо/вниз → в клетку приходят только сверху или слева → это динамика.
dp[i][j] = grid[i][j] + max/min(сосед сверху, сосед слева), заполнять слева-направо, сверху-вниз.
Ответ — правая нижняя клетка; для минимума и максимума делают два прохода.