Динамика

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ДП по профилю

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

ДП по цифрам

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