Динамика

Динамика

Kostya Amelichev

Динамика - это одна из самых сложных для моего понимания тем.

Как работает динамика?

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

Что в динамике нужно?

  1. Придумать состояния
  2. Расписать переходы
  3. Проинициализировать
  4. Придумать порядок обхода
  5. Понять, где лежит ответ


Самые баянистые задачи на динамику:

  1. Кузнечик/Фиббоначи
  2. НВП
  3. Черепашка

Какие разновидности ДП бывают:

ДП по подстрокам

стандартно dp[l][r] с порядком пересчета по длине

ДП по подмножествам

Перебираем маски и делаем переходы в новые состояния

ДП по поддеревьям

Делаем дфс с пересчетом от сыновей

ДП по профилю

Есть по обычному - мы перебираем переходы между масками и возводим маску в степень. Есть по изломанному - мы просто заполняем табличку последовательно, храним маску и позицию

ДП по цифрам

Последовательно кидаем циферки и смотрим на ответ. Самое важное аккуратно получать ответ - там такое себе, часто надо правильно перебрать состояния меньшие чем Н