Динамическое программирование: рюкзак и другие задачи
Как понять, что задача решается через ДП, чем отличается «сверху вниз» от «снизу вверх», разбор задачи о рюкзаке и восстановление ответа.
Динамическое программирование применимо, когда задача разбивается на подзадачи, эти подзадачи перекрываются, и оптимальное решение целого строится из оптимальных решений частей. Если подзадачи не повторяются — это обычная рекурсия или «разделяй и властвуй».
Два способа записи
# сверху вниз — рекурсия + мемоизация
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
return n if n < 2 else fib(n - 1) + fib(n - 2)
# снизу вверх — таблица
def fib_dp(n):
dp = [0, 1]
for i in range(2, n + 1):
dp.append(dp[i - 1] + dp[i - 2])
return dp[n]Без мемоизации наивная рекурсия для Фибоначчи это O(2ⁿ), с ней — O(n). Это самый наглядный пример того, что даёт ДП.
Задача о рюкзаке 0/1
Есть n предметов с весами w и стоимостями c, рюкзак вместимостью W. Каждый предмет берём целиком или не берём. Максимизируем суммарную стоимость.
dp[i][j] = max( dp[i-1][j], dp[i-1][j - w[i]] + c[i] ), если j ≥ w[i]
def knapsack(w, c, W):
n = len(w)
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(W + 1):
dp[i][j] = dp[i - 1][j]
if j >= w[i - 1]:
dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i - 1]] + c[i - 1])
return dp[n][W]Восстановление набора предметов
def restore(dp, w, W):
items, j = [], W
for i in range(len(w), 0, -1):
if dp[i][j] != dp[i - 1][j]: # предмет i брали
items.append(i - 1)
j -= w[i - 1]
return items[::-1]Другие типовые задачи
| Задача | Состояние dp | Сложность |
|---|---|---|
| Лестница (число способов) | dp[i] — способов дойти до ступени i | O(n) |
| Наибольшая общая подпоследовательность | dp[i][j] — НОП префиксов длины i и j | O(n·m) |
| Наибольшая возрастающая подпоследовательность | dp[i] — длина НВП, оканчивающейся в i | O(n²) или O(n log n) |
| Размен монетами | dp[s] — минимум монет на сумму s | O(n·S) |
| Расстояние Левенштейна | dp[i][j] — правок для префиксов | O(n·m) |
Как оформлять в отчёте
- Сформулируйте, что именно означает dp[i][j] — одним предложением. Это половина оценки.
- Выпишите рекуррентное соотношение и базу.
- Укажите порядок обхода: почему считаем именно в такой последовательности.
- Оцените время и память, покажите оптимизацию памяти до одномерного массива, если она возможна.
Частые вопросы
Чем ДП отличается от жадного алгоритма?
Жадный делает локально лучший выбор и не пересматривает его — работает не всегда. ДП перебирает варианты, сохраняя результаты, и гарантирует оптимум там, где выполняется принцип оптимальности.
Как ужать память в рюкзаке?
Хранить только текущую и предыдущую строку либо один массив, обновляя его справа налево — получится O(W) вместо O(n·W). Но тогда сложнее восстановить сам набор.