Определение состояния и перехода

Любое DP начинается с определения состояния: что именно представляет собой dp[i]? Сформулируйте это правильно — и остальное последует само.

Опишите смысл словами: dp[i] = ответ для первых i элементов. Нечёткое определение состояния приводит к ошибочному рекуррентному соотношению.

Переход показывает, как dp[i] строится из предыдущих состояний. Это рекуррентное уравнение, лежащее в основе решения.

Базовые случаи — это наименьшие состояния, значения которых известны напрямую. Без правильной основы все последующие значения окажутся неверными.

Каждое состояние нужно заполнить после состояний, от которых оно зависит. Это правило зависимостей определяет направление цикла.

Определите, в какой ячейке хранится итоговый результат. Часто это dp[n], но иногда ответом является максимум по всей таблице.

Количество различных состояний определяет Ваше ограничение по времени. Одномерный массив dp для n элементов содержит O(n) состояний, которые нужно заполнить.

Общее время равно числу состояний, умноженному на работу для одного перехода. Переход за O(n) внутри n состояний даёт O(n в квадрате).

Если одного индекса недостаточно, чтобы описать ситуацию, добавьте ещё один. Второе измерение превращает dp[i] в dp[i][j].

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

Состояние, переход, базовый случай, порядок, ответ. Определите эти пять составляющих — и почти любое рекуррентное соотношение DP встанет на свои места.

Вы проектируете DP. Что означает dp[i]?

Теперь Вы умеете определять состояние, записывать его переход, задавать базовые случаи и находить ответ. Этот план превращает DP из подбора решений в последовательный алгоритм.