Задание 18 ЕГЭ по информатике

Теория к заданию 18 ЕГЭ по информатике: динамическое программирование на поле

Задание с файлом: Робот идёт по таблице, собирая монеты. Нужно найти максимальную и минимальную сумму.

Что нужно знать

• Задача решается динамическим программированием: в каждую клетку можно прийти только сверху или слева.
• Формула перехода: dp[i][j] = a[i][j] + max(dp[i−1][j], dp[i][j−1]) для максимума и с min для минимума.
• Первую строку и первый столбец заполняют накопительной суммой.
• Стены запрещают переход между соседними клетками, поэтому такие переходы исключают из максимума или минимума.
• Конечными считаются клетки, из которых нельзя двигаться дальше; ответ ищут среди них.

Динамическое программирование на таблице

• Робот обычно ходит только вправо и вниз, значит, в каждую клетку можно попасть лишь сверху или слева.
• Заводим вторую таблицу той же формы и заполняем её слева направо и сверху вниз.
• Формула для максимума: D[i][j] = A[i][j] + max(D[i−1][j], D[i][j−1]).
• Для минимума та же формула с min вместо max.
• Первая строка и первый столбец заполняются накопительной суммой, потому что там выбора нет.
• Стены и запрещённые клетки обозначайте значением, которое заведомо хуже (минус бесконечность для максимума).
• Ответ лежит в правой нижней клетке вспомогательной таблицы.
• Всё это удобнее сделать в электронной таблице: формула пишется один раз и растягивается.

Как решать задание 18

1. Постройте таблицу того же размера для накопленных сумм.
2. Заполните первую строку и первый столбец с учётом стен.
3. Заполняйте остальные клетки по формуле перехода, пропуская запрещённые направления.
4. Найдите все конечные клетки и выберите среди них экстремумы.
5. Запишите сначала максимум, затем минимум.

Разбор примера

Частые ошибки

• Ищут ответ только в правой нижней клетке, забыв про другие конечные клетки.
• Не учитывают внутренние стены при построении таблицы.