Одномерное динамическое программирование
Одномерное динамическое программирование — это способ решения задачи, при котором для каждого значения одного параметра вычисляют и сохраняют лучший или возможный результат. Обычно параметром служит номер элемента последовательности, длина пройденного пути или количество выполненных шагов.
Как устроено решение
Сначала выбирают состояние динамического программирования: что означает \(dp[i]\). Затем задают начальные значения и правило перехода. После этого таблицу заполняют в порядке, при котором все нужные предыдущие элементы уже известны. Последний элемент таблицы обычно содержит ответ.
Пусть разрешено подняться по лестнице на 1 или 2 ступеньки за ход. Обозначим \(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[4]=5\). Значит, на четвёртую ступеньку можно попасть пятью способами.
Если состояние зависит от двух независимых параметров, например от номера строки и номера столбца, нужна двумерная динамика с таблицей \(dp[i][j]\). В одномерном ДП достаточно одного индекса, хотя переход может использовать несколько предыдущих значений.
Что обычно означает запись \(dp[i]\) в одномерном динамическом программировании?
В задачах на минимум или максимум таблица хранит не количество способов, а лучшее значение: например, минимальную стоимость пути к позиции \(i\). Важно точно определить смысл \(dp[i]\), иначе даже правильная формула даст неверный ответ.
Главное
- Одномерное ДП использует таблицу с одним индексом \(dp[i]\).
- Решение состоит из состояния, начальных значений и перехода.
- Каждое новое значение строится по уже вычисленным состояниям; смысл таблицы может быть разным: число способов, минимум, максимум или достижимость.