Переход динамического программирования
Переход динамического программирования — это правило, по которому значение одного состояния вычисляют через значения уже известных состояний. Переход показывает, как маленькие подзадачи объединяются в решение исходной задачи.
Общий вид формулы
Здесь \(s\) — текущее состояние, \(p\) — предыдущее состояние, а \(\operatorname{cost}(p \to s)\) — вклад перехода. Для задач на количество способов обычно складывают варианты, для задач на лучший результат берут минимум или максимум. Начальные значения задаются отдельно: это базовые состояния, для которых ответ известен сразу.
Пусть за один шаг можно подняться на одну или две ступеньки. Состояние \(dp[i]\) — число способов попасть на ступеньку \(i\). На неё приходят со ступеньки \(i-1\) или \(i-2\), поэтому переход имеет вид \(dp[i]=dp[i-1]+dp[i-2]\). При \(dp[0]=1\) и \(dp[1]=1\) получаем \(dp[2]=2\), \(dp[3]=3\): способы действительно перечисляются без пропусков и повторов.
Переход — это математическая зависимость между состояниями, а порядок вычисления — способ реализовать её в программе. Обычно состояния считают от меньших к большим, но в некоторых задачах используют рекурсию с запоминанием. Важно, чтобы каждое состояние было вычислено после всех состояний, от которых оно зависит.
В задаче \(dp[i]\) — минимальная стоимость достижения позиции \(i\), на один шаг можно перейти из \(i-1\) или \(i-2\). Какой переход верен?
Главное
- Переход связывает текущее состояние с предыдущими и описывает все способы попасть в него.
- Операция в формуле зависит от цели: сумма считает варианты, минимум или максимум выбирает лучший.
- Корректность проверяют так: каждый допустимый путь должен быть учтён ровно один раз, а недопустимые — не должны попасть в формулу.