Динамическое программирование по таблице: максимальная и минимальная сумма на маршруте.
Робот идёт по клетчатому полю и собирает значения. Если разрешены движения вправо и вниз, лучший результат в клетке зависит только от клетки сверху и слева.
В клетку можно прийти слева.
В клетку можно прийти сверху.
Для максимума: dp[i][j]=cell+max(top,left). Для минимума — min.
Стены или запрещённые клетки нужно помечать как недостижимые. Не подставляйте для них 0: это может создать ложный «выгодный» путь.
dp[0][0] равно значению начальной клетки.
В первой строке путь только слева, в первом столбце — только сверху.
Добавляй значение клетки к лучшему из доступных предшественников.
Недостижимые клетки не участвуют в max/min.
Для минимума нужна отдельная таблица или другой проход.
Поле 4×4 содержит монеты. Робот стартует слева сверху и может идти только вправо или вниз. Какова максимальная сумма к правой нижней клетке?
Каждое число — количество монет в клетке.
После заполнения таблицы максимумов в правой нижней клетке получается 21.
Накопленные суммы: 2, 3, 6, 7.
Например для клетки со значением 6: max(8 сверху, 9 слева)+6=15.
Последняя строка максимумов заканчивается значением 21.
Ответь на оба вопроса. Проверка работает прямо в браузере; правильные ответы автоматически отмечают практику выполненной.
Тематика урока сверена с актуальным каталогом ЕГЭ‑2026; примеры и тренажёры ТурбоУроки составлены самостоятельно. Каталог заданий ↗