Оптимизация динамического программирования

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

Что именно оптимизируют

В динамическом программировании обычно задают состояние динамического программирования \(dp[i]\) или \(dp[i][j]\), а затем вычисляют его по переходу динамического программирования. Основные характеристики алгоритма — число состояний \(S\), число переходов из одного состояния \(K\) и объём памяти \(M\).

Оптимизация может уменьшить память с \(O(nm)\) до \(O(m)\), время — с \(O(nmK)\) до \(O(nm)\), а иногда и число рассматриваемых состояний. Важно не менять смысл состояния: сначала нужно понять, от каких уже вычисленных значений действительно зависит новый ответ.

Сокращение памяти: хранить только нужный слой

Рассмотрим таблицу \(dp[i][j]\), где \(i\) — номер обработанного предмета, шага или строки, а \(j\) — ёмкость, сумма или другой параметр. Если значения строки \(i\) зависят только от строки \(i-1\), нет смысла хранить все строки. Достаточно двух массивов: previous и current.

Иногда можно обойтись даже одним массивом. Тогда порядок перебора критичен. Если новое значение должно использовать старое \(dp[j]\), параметр \(j\) перебирают справа налево. При переборе слева направо уже обновлённое значение может быть использовано повторно, и получится другая задача.

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

Пример: рюкзак с одним массивом

Есть \(n\) предметов. У предмета \(i\) масса \(w_i\) и ценность \(v_i\). Вместимость рюкзака равна \(W\). Требуется получить максимальную ценность, не превышающую вместимость. Полная таблица \(dp[i][s]\) хранит ответ после рассмотрения первых \(i\) предметов при вместимости \(s\).

Первый вариант означает «не брать предмет», второй — «взять предмет». Для \(s<w_i\) предмет взять нельзя, поэтому значение не меняется. Поскольку переход обращается к строке \(i-1\), заменим две строки одним массивом \(dp[s]\) и будем обновлять вместимость справа налево.

def knapsack(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for weight, value in zip(weights, values):
        for s in range(capacity, weight - 1, -1):
            dp[s] = max(dp[s], dp[s - weight] + value)
    return dp[capacity]

Время работы этого решения — \(O(nW)\), память — \(O(W)\). Полная таблица потребовала бы \(O(nW)\) памяти. Если нужно восстановить сами выбранные предметы, одной строки может быть недостаточно: придётся хранить решения, повторно вычислять часть таблицы или применять специальное восстановление пути.

Сокращение времени и числа состояний

Первый приём — не перебирать невозможные состояния. Например, если после нескольких шагов достижимы только суммы из множества \(R\), можно обрабатывать только их. Для задач на суммы удобно хранить логический массив достижимости или множество, но множество может иметь больший константный множитель.

Второй приём — использовать границы. Если параметр суммы не может превышать общий лимит, не нужно создавать массив большего размера. Если после \(i\) шагов максимальная возможная сумма равна \(P_i\), цикл достаточно вести до \(\min(W,P_i)\). Аналогично нижняя граница может исключить часть состояний.

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

Если каждый переход перебирает много вариантов, ищут структуру: монотонность, минимум на отрезке, повторяющиеся значения. Тогда обычный перебор можно заменить префиксными суммами, очередью, двоичным поиском или другой структурой данных. Это уже не механическое сокращение таблицы, а оптимизация формулы перехода.

Типичные ошибки и проверка результата

Проверяйте оптимизированную программу на маленьких данных, где можно построить полную таблицу. Сравните ответы для случайных наборов и отдельно проверьте крайние случаи: нулевую вместимость, предмет тяжелее лимита, пустой набор, одинаковые веса и максимальные значения.