№ 18. Робот на клетчатом поле (ДП в таблице)

Главное

Робот идёт вправо и вниз, собирая монеты. Максимальная/минимальная сумма — динамикой: в клетке max(слева, сверху) + значение.

Правила

1. dp[i][j] = max(dp[i−1][j], dp[i][j−1]) + a[i][j]
2. Стены — ограничения
3. Считаем от угла

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

Как вычисляется значение в клетке для максимальной суммы?

Максимум из левого и верхнего плюс монеты клетки

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

• Считать путь «жадно», выбирая только соседнюю большую клетку.

Потренироваться

Задания с проверкой и подсказками, схема темы и разбор ошибок с ИИ-репетитором — в уроке на платформе.