Двумерное ДП : черепашка
Заплываем в двумерное ДП.
Задача про черепашку
Эволюционируем от кузнечика к черепахе. Черепашка перемещается по прямоугольному полю $n \times m$ и собирает цветочки. На клетке $(i,j)$ растет $c_{ij}$ цветочков. Изначально черепашка стоит в клетеке $(0,0)$, а ей надо добраться до клетки $(n-1, m-1)$, собрав как можно больше цветочков. Двигаться она может только на одну клетку вниз или на одну клетку вправо за раз. По диагонали она ходить не умеет :(
Решение во многом похоже на задачу про кузнечика:
- $dp[i][j]$ - состояние динамики, равное максимальному количеству цветочков, которое можно набрать по пути до клетки $(i, j)$.
- $dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + c_{ij}$ - правило пересчета
- Порядок обхода - надо проходить через клетки так, чтобы все состояния, которые нужны для пересчета, уже были валидны. Можно во внешнем цикле перебирать строку, а во внутреннем столбец по возрастанию.
- Восстановление ответа аналогично задаче про кузнечика.
Расход времени и памяти составит $O(nm)$.
Количество путей
Забудем пока про цветочки. Пусть теперь неокторые клетки поля заблокированы, черепашка не может заходить на них. Мы хотим найти, сколькими способами черепашка может добраться до клетки $(n-1,m-1)$.
Пусть $dp[i][j]$ - количество способов добраться до клетки $(i, j)$ из начальной. Формула пересчета тогда будет следующей: $dp[i][j] = dp[i - 1[j] + dp[i][j - 1]$. То есть в клетку $(i, j)$ можно пройти либо из клетки над ней, либо слева от нее.
Заметим, что такое правило пересчета разрешает нам ходить по заблокированным клеткам в общем случае. Это можно исправить так: при обходе поля и подсчете состояний можно не считать способы для заблокированных клеток, значение динамики в них всегда будет $0$, что равносильно запрету посещать клетку.
Какие стартовые значения нам нужны? Пока что мы знаем только, что в исходную клетку можно пройти единственным способом - остаться в ней, поэтому $dp[0][0] = 1$.
Автор конспекта: Полина Романченко
По всем вопросам пишите в telegram @Romanchenko