Как решать задание 18 ЕГЭ по информатике — робот на таблице и динамическое программирование

О чём задание

Задание 18 — это классика динамического программирования в ЕГЭ по информатике. Тебе дают таблицу чисел размером N×M. Робот стартует в левом верхнем углу (клетка (0, 0)) и должен добраться до правого нижнего угла (клетка (N-1, M-1)). Разрешённые ходы:

• Вправо — переход из (i, j) в (i, j+1)
• Вниз — переход из (i, j) в (i+1, j)

Робот собирает числа из клеток, через которые проходит (включая стартовую и финишную). Типичные варианты вопроса:

1. Максимальная сумма собранных чисел
2. Минимальная сумма собранных чисел
3. Количество различных путей из старта в финиш
4. То же, но с запрещёнными клетками (в них нельзя заходить)

Все четыре варианта решаются одним и тем же методом — динамическим программированием по таблице.

Идея динамического программирования

ДП — это способ решения задач, когда ответ для всей задачи выражается через ответы на подзадачи меньшего размера. В нашем случае подзадача — «максимальная сумма пути из (0, 0) в клетку (i, j)». Обозначим её dp[i][j].

Ключевое наблюдение: в клетку (i, j) робот мог прийти ровно двумя способами — сверху (из (i-1, j)) или слева (из (i, j-1)). Значит, максимальная сумма до (i, j) равна:

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

Для минимальной суммы — то же самое, но с min. Для количества путей — сложение:

dp[i][j] = dp[i-1][j] + dp[i][j-1]

База рекурсии

В клетку (0, 0) робот уже стоит, собирать нечего кроме самой клетки:

dp[0][0] = table[0][0]

В первую строку (i = 0) робот может попасть, только двигаясь вправо от (0, 0). Значит:

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

В первый столбец (j = 0) — только вниз:

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

Это критично. Если забыть про инициализацию и начать заполнять формулой с max/min, формула обратится к несуществующей клетке и выдаст мусор.

Разбор примера — таблица 4×4

Возьмём таблицу:

i \ j	0	1	2	3
0	3	1	5	2
1	2	7	4	1
2	4	3	8	6
3	1	5	2	9

Вопрос: максимальная сумма чисел на пути робота из (0, 0) в (3, 3), если он ходит только вправо и вниз.

Шаг 1 — заполняем первую строку

В первую строку робот идёт только вправо:

• dp[0][0] = 3
• dp[0][1] = 3 + 1 = 4
• dp[0][2] = 4 + 5 = 9
• dp[0][3] = 9 + 2 = 11

Шаг 2 — заполняем первый столбец

В первый столбец робот идёт только вниз:

• dp[0][0] = 3
• dp[1][0] = 3 + 2 = 5
• dp[2][0] = 5 + 4 = 9
• dp[3][0] = 9 + 1 = 10

Шаг 3 — заполняем остальное по формуле

Для каждой клетки dp[i][j] = table[i][j] + max(dp[i-1][j], dp[i][j-1]):

• dp[1][1] = 7 + max(4, 5) = 7 + 5 = 12
• dp[1][2] = 4 + max(9, 12) = 4 + 12 = 16
• dp[1][3] = 1 + max(11, 16) = 1 + 16 = 17
• dp[2][1] = 3 + max(12, 9) = 3 + 12 = 15
• dp[2][2] = 8 + max(16, 15) = 8 + 16 = 24
• dp[2][3] = 6 + max(17, 24) = 6 + 24 = 30
• dp[3][1] = 5 + max(15, 10) = 5 + 15 = 20
• dp[3][2] = 2 + max(24, 20) = 2 + 24 = 26
• dp[3][3] = 9 + max(30, 26) = 9 + 30 = 39

Таблица dp полностью

i \ j	0	1	2	3
0	3	4	9	11
1	5	12	16	17
2	9	15	24	30
3	10	20	26	39

Ответ — 39. Это число в правом нижнем углу. Оно и есть максимальная сумма.

Если нужно восстановить сам путь — посмотри, откуда в каждую клетку пришли (сверху или слева), и пройди обратно от (3, 3) до (0, 0). Но в ЕГЭ обычно просят только число.

Решение через LibreOffice Calc

На КЕГЭ у тебя есть LibreOffice Calc — и для задания 18 это, пожалуй, самый быстрый способ. Алгоритм:

1. Скопируй таблицу в Calc

Размести её в диапазоне A1:D4 (для таблицы 4×4). Каждое число — в отдельной ячейке.

2. Создай второй лист для dp

Переключись на второй лист (или используй диапазон F1:I4 того же листа). Это будет твоя таблица dp.

3. Заполни первую строку и первый столбец

В F1 напиши =A1. В G1 — =F1 + B1. В H1 — =G1 + C1. В I1 — =H1 + D1. Потом растяни или введи аналогично первый столбец вниз.

Быстрее всего так: в F1 напиши =A1, в G1 напиши =F1+B1, в F2 напиши =F1+A2. Теперь у тебя база готова.

4. Формула для остальных ячеек

В G2 напиши:

=B2 + MAX(F2; G1)

Ключевая идея — MAX(F2; G1) берёт максимум из «пришли сверху» (G1) и «пришли слева» (F2). К нему прибавляешь значение текущей клетки (B2 — это значение исходной таблицы).

5. Растягивай

Скопируй ячейку G2 и вставь в диапазон G2:I4. Calc автоматически сдвинет ссылки. В ячейке I4 будет ответ — 39.

Приём мощный, потому что ты работаешь с визуальной таблицей, легко проверить любую ячейку и быстро изменить подход (заменить MAX на MIN, добавить проверку запрещённых клеток через IF).

Решение на Python

Python-решение универсальнее и короче. Вот полный код для максимальной суммы:

table = [
    [3, 1, 5, 2],
    [2, 7, 4, 1],
    [4, 3, 8, 6],
    [1, 5, 2, 9],
]

N = len(table)
M = len(table[0])

dp = [[0] * M for _ in range(N)]
dp[0][0] = table[0][0]

# первая строка
for j in range(1, M):
    dp[0][j] = dp[0][j-1] + table[0][j]

# первый столбец
for i in range(1, N):
    dp[i][0] = dp[i-1][0] + table[i][0]

# остальное
for i in range(1, N):
    for j in range(1, M):
        dp[i][j] = table[i][j] + max(dp[i-1][j], dp[i][j-1])

print(dp[N-1][M-1])  # 39

Для минимальной суммы замени max на min. Для количества путей — код ещё короче:

dp = [[0] * M for _ in range(N)]
dp[0][0] = 1

for j in range(1, M):
    dp[0][j] = dp[0][j-1]
for i in range(1, N):
    dp[i][0] = dp[i-1][0]

for i in range(1, N):
    for j in range(1, M):
        dp[i][j] = dp[i-1][j] + dp[i][j-1]

print(dp[N-1][M-1])

Вариант с запрещёнными клетками

Допустим, клетка (1, 2) запрещена. Достаточно проверки:

blocked = {(1, 2)}

for i in range(N):
    for j in range(M):
        if (i, j) in blocked:
            dp[i][j] = 0   # для количества путей
            # dp[i][j] = float('-inf')  # для максимальной суммы
            continue
        if i == 0 and j == 0:
            dp[i][j] = table[i][j]
        elif i == 0:
            dp[i][j] = dp[i][j-1] + table[i][j]
        elif j == 0:
            dp[i][j] = dp[i-1][0] + table[i][j]
        else:
            dp[i][j] = table[i][j] + max(dp[i-1][j], dp[i][j-1])

Для максимальной суммы в запрещённых клетках ставь -∞ — тогда формула с max сама их проигнорирует. Для количества путей — ноль.

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

Иногда на ЕГЭ таблица лежит в .txt или .csv файле. Считать её на Python проще всего так:

with open('18.txt') as f:
    table = [list(map(int, line.split())) for line in f]

N = len(table)
M = len(table[0])

Это работает, если числа разделены пробелами или табуляцией. Если разделитель — запятая, используй line.split(',').

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

1. Забыл инициализировать первую строку/столбец

Самая частая ошибка. Код отрабатывает без ошибок рантайма, но выдаёт мусор, потому что dp[0][j-1] (при j > 0) ещё равно нулю, и первая строка заполнится как 0 + table[0][j] вместо накопительной суммы. Всегда сначала инициализируй края, потом заполняй внутренность.

2. Перепутал max и min

Проверяй условие дважды. «Наибольшая сумма» — это max. «Наименьшая сумма» — min. «Количество путей» — сложение. Если пишешь в Calc, удобно сделать шаблон сразу с MAX, а переключать на MIN одним Find & Replace.

3. Перепутал координаты — (i, j) vs (j, i)

В Python table[i][j] — это i-я строка и j-й столбец. В математической записи (x, y) первая координата обычно горизонтальная. Робот ходит вправо — это увеличение j, вниз — увеличение i. Если напишешь наоборот, получишь транспонированную картинку.

4. Границы цикла

Циклы должны быть for i in range(N) и for j in range(M), а не наоборот. И внутренний цикл должен стартовать с 1, если внешний тоже с 1 — иначе попадёшь на клетки первой строки и первого столбца, которые уже инициализированы.

5. Целочисленная проблема в Calc

LibreOffice Calc иногда показывает число в экспоненциальной форме (типа 1.23E+08). Растяни столбец пошире или поставь формат «Число» без десятичных — иначе в ответе опечатаешься на порядок.

Тайминг

Этап	Время
Прочитать и понять условие	1 минута
Ввести таблицу в Calc	2-3 минуты
Заполнить формулы и получить ответ	1-2 минуты
Перепроверить	1 минута
Итого	5-7 минут

Если пишешь на Python, первые два пункта занимают вместе 3-4 минуты (если таблица большая — больше, если читаешь из файла — меньше). В любом случае задание 18 должно идти в группе «быстрых»: план 90+ баллов предполагает решение 18-го за 5 минут максимум.

Связь с другими заданиями

Задание 18 тренирует табличное ДП — базовую технику, которая появляется и в 22-м (исполнитель с разрешёнными переходами), и в 26-м (оптимизация), и частично в 27-м (если решать через динамику). Если ты уверенно решаешь 18, ты на полпути к пониманию более сложных задач.

Сравни: задание 12 тоже работает с клеточной структурой (исполнитель Редактор), но там другая идея. А задание 6 с Черепахой тренирует работу с координатной плоскостью — это уровень ниже, но полезный фундамент.

Шаблон на экзамен

Заведи в голове (или распечатай перед экзаменом, если можно) такой шаблон на Python — чтобы не тратить время на пустом месте:

with open('18.txt') as f:
    table = [list(map(int, line.split())) for line in f]

N, M = len(table), len(table[0])
dp = [[0] * M for _ in range(N)]
dp[0][0] = table[0][0]
for j in range(1, M): dp[0][j] = dp[0][j-1] + table[0][j]
for i in range(1, N): dp[i][0] = dp[i-1][0] + table[i][0]
for i in range(1, N):
    for j in range(1, M):
        dp[i][j] = table[i][j] + max(dp[i-1][j], dp[i][j-1])
print(dp[N-1][M-1])

Меняешь max на min, файл на нужный, и готово. Меньше минуты на набор кода, если пальцы помнят. Идиомы Python для ЕГЭ помогут сократить ещё сильнее.

Что попрактиковать

1. Реши 5-7 задач на максимальную сумму из банка ФИПИ
2. Реши 3-4 задачи на минимальную сумму
3. Реши 2-3 задачи на количество путей
4. Реши 1-2 задачи с запрещёнными клетками
5. Попробуй вариант с диагональным ходом (3 направления)

После этого задание 18 будет решаться на автомате за 4-5 минут. Если прорабатываешь систематически — смотри план подготовки на 3 месяца.

Итоги

• Задание 18 — чистое динамическое программирование по таблице
• Формула для max-суммы: dp[i][j] = table[i][j] + max(dp[i-1][j], dp[i][j-1])
• Для min-суммы — min, для количества путей — сложение
• На экзамене быстрее всего решать в LibreOffice Calc; Python универсальнее
• Обязательно инициализируй первую строку и первый столбец отдельно
• Рекомендуемое время — 5-7 минут
• Стоимость — 1 первичный балл

Освоишь 18-е — получишь базу для понимания всей темы ДП, которая даёт ещё 2-4 балла в других заданиях. Это одна из самых высокоокупаемых тем для тренировки.