Задача про черепашку

Давайте вспомним задачу про кузнечика с прошлого занятия и рассмотрим аналогичную задачу, но уже не на прямой, а в прямоугольной таблице.

Есть поле из $n$ на $m$ клеточек. Чтобы побывать в клетке $(i, j)$, нужно заплатить $a[i][j]$ монет. Черепашка начинает в клетке $(0, 0)$ и хочет попасть в клетку $(n, m)$. Черепаха умеет ползти на одну клетку вправо или на одну клетку вниз.

За какое минимальное число монет она сможет это сделать?

Решим задачу по стандартному плану:

• Сформулировать, что будет хранить каждое состояние.

  По аналогии с задачей про кузнечика, $dp[i][j]$ - минимальное число монет, чтобы дойти до клетки $(i, j)$.

• Найти формулу перехода.

  Есть два способа попасть в текущую клетку: сверху или слева.

  Значит, $dp[i][j] = a[i][j] + min(dp[i - 1][j], dp[i][j - 1])$.

  Обратите внимание, что для крайних клеток будет всего один способ перехода.

• Определить порядок пересчета.

  Чтобы пересчитать текущее состояние, нужно знать $dp[i - 1][j]$ и $dp[i][j - 1]$. Поэтому удобнее всего будет идти последовательно заполняя строки (те сначала цикл по $i$, а потом по $j$)

• Задать значения базы динамики.

  $dp[0][0] = a[0][0]$

• Понять, где лежит ответ.

  $dp[n][m]$

Задача про лесенки

Вам дано $n$ кубиков, необходимо посчитать, сколькими способами можно сложить из них лесенку - структуру, в которой в каждом горизонтальном слое кубиков меньше, чем в предыдущем.

Воспользуемся стандартным планом:

• Сформулировать, что будет хранить каждое состояние.

  Создадим массив $dp[i][j]$ - количество лесенок из $i$ кубиков, у которых на нижнем (самом большом) уровне ровно $j$ кубиков.

• Найти формулу перехода.

  Во-первых, $dp[i][j]$ содержит все способы, содержащиеся в $dp[i - 1][j - 1]$, потому что к каждому из них можно добавить кубик на нижнем уровне. Во-вторых, мы можем положить новый слой размера $j$ и поставить сверху лесенку из $i - j$ кубиков, у которой на последнем уровне $j - 1$ кубик.

  Итоговая формула - $dp[i][j] = dp[i - 1][j - 1] + dp[i - j][j - 1]$.

• Задать значения базы динамики.

  $dp[1][1] = 1$, остальные значения равны нулю.

• Понять, где лежит ответ.

  Нетрудно догадаться, что ответ - сумма $dp[n][k]$ по всем $k$ от $1$ до $n$ включительно.