- Писать функцию с базовым случаем и рекурсивным шагом и отслеживать стек вызовов
- Узнавать задачи, решаемые ДП, и составлять для них рекуррентное соотношение
- Заполнять таблицы для рюкзака и НОП и восстанавливать оптимальное решение
- Показывать, когда жадный алгоритм ошибается
Если запрограммировать числа Фибоначчи прямо по формуле F(n) = F(n − 1) + F(n − 2), то для F(40) компьютер сделает больше ста миллионов вызовов функции. А добавив всего несколько строк, та же программа мгновенно найдёт и F(90). В этом уроке мы разберём, как работает это «волшебство» — динамическое программирование, — начав с его основы, рекурсии.
Рекурсия и стек вызовов
Решение задачи функцией через её же уменьшенную копию. У каждой рекурсивной функции две части: базовый случай (ответ известен сразу, рекурсия останавливается) и рекурсивный шаг (задача уменьшается в сторону базового случая).
- n · (n − 1)!рекурсивный шаг
- 0! = 1базовый случай
Функция fact(n) возвращает 1 при n == 0 и n * fact(n - 1) иначе. Что происходит в стеке при вызове fact(4)?
Показать решениеСкрыть решение
fact(4) → fact(3) → fact(2) → fact(1) → fact(0) = 1 — базовый случай, в стеке 5 кадров.
Подъём (кадры закрываются в обратном порядке):
fact(1) = 1 · 1 = 1
fact(2) = 2 · 1 = 2
fact(3) = 3 · 2 = 6
fact(4) = 4 · 6 = 24.
Время O(n), память стека тоже O(n): каждый вызов ждёт в стеке своего ответа.
Перекрывающиеся подзадачи и мемоизация
В простой рекурсивной версии fib(5) дважды вызывает fib(3) и трижды fib(2) — одни и те же подзадачи решаются снова и снова. Число вызовов растёт экспоненциально, как и сам ответ: calls(n) = 2F(n + 1) − 1. Мемоизация (сверху вниз) хранит ответ каждой подзадачи в словаре и не вычисляет его повторно; табуляция (снизу вверх) заполняет ответы циклом от малых к большим.
- T(n)время работы простой рекурсивной fib(n)
- φзолотое сечение
С мемоизацией каждое fib(k) вычисляется один раз: n + 1 подзадача × O(1) работы = O(n). От экспоненты к линии!
from functools import lru_cache
calls = 0
def fib_naive(n):
global calls
calls += 1
return n if n < 2 else fib_naive(n - 1) + fib_naive(n - 2)
@lru_cache(maxsize=None)
def fib_memo(n):
return n if n < 2 else fib_memo(n - 1) + fib_memo(n - 2)
def fib_table(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
print(fib_naive(25), 'naive calls:', calls)
print(fib_memo(25), 'memo calls:', fib_memo.cache_info().misses)
print(fib_table(90))▸ Ожидаемый результат
75025 naive calls: 242785 75025 memo calls: 26 2880067194370816120
lru_cache вычисляется всего 26 различных подзадач. Табличная версия мгновенно находит F(90) с памятью O(1).Классическое ДП: рюкзак и НОП
Задача о рюкзаке 0/1: выбери из предметов с весами wᵢ и стоимостями vᵢ такие, чтобы в рюкзак вместимостью W поместилась максимальная суммарная стоимость (каждый предмет либо берём, либо нет). Для i-го предмета два варианта — не брать или взять; оставляем лучший.
- dp[i][c]наибольшая стоимость из первых i предметов при вместимости c
- wᵢ, vᵢвес и стоимость i-го предмета (второй вариант только при wᵢ ≤ c)
Время и память O(n · W). Это псевдополиномиальная сложность: она экспоненциальна по числу битов W.
W = 5. Предметы (вес, стоимость): 1: (1, 1), 2: (2, 3), 3: (3, 4), 4: (4, 5). Найди наибольшую стоимость и выбранные предметы.
Показать решениеСкрыть решение
i = 1: [0, 1, 1, 1, 1, 1]
i = 2: [0, 1, 3, 4, 4, 4] (например, c = 3: max(1, dp[1][1] + 3 = 4) = 4)
i = 3: [0, 1, 3, 4, 5, 7] (c = 5: max(4, dp[2][2] + 4 = 7) = 7)
i = 4: [0, 1, 3, 4, 5, 7] (c = 5: max(7, dp[3][1] + 5 = 6) = 7)
Ответ dp[4][5] = 7.
Восстановление: dp[4][5] = dp[3][5] → предмет 4 не взят; dp[3][5] = 7 ≠ dp[2][5] = 4 → предмет 3 взят, c = 5 − 3 = 2; dp[2][2] = 3 ≠ dp[1][2] = 1 → предмет 2 взят, c = 0.
Выбор: предметы 2 и 3 (вес 2 + 3 = 5, стоимость 3 + 4 = 7).
def knapsack(items, W):
n = len(items)
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i, (w, v) in enumerate(items, start=1):
for c in range(W + 1):
dp[i][c] = dp[i - 1][c]
if w <= c:
dp[i][c] = max(dp[i][c], dp[i - 1][c - w] + v)
chosen, c = [], W
for i in range(n, 0, -1):
if dp[i][c] != dp[i - 1][c]:
chosen.append(i)
c -= items[i - 1][0]
return dp[n][W], sorted(chosen), dp
best, chosen, dp = knapsack([(1, 1), (2, 3), (3, 4), (4, 5)], 5)
for row in dp:
print(row)
print('best value:', best, '| items:', chosen)▸ Ожидаемый результат
[0, 0, 0, 0, 0, 0] [0, 1, 1, 1, 1, 1] [0, 1, 3, 4, 4, 4] [0, 1, 3, 4, 5, 7] [0, 1, 3, 4, 5, 7] best value: 7 | items: [2, 3]
Наибольшая общая подпоследовательность (НОП, LCS): самая длинная последовательность символов, встречающаяся в обеих строках в одном и том же порядке (не обязательно подряд). Для «ABCBDAB» и «BDCABA» длина НОП равна 4, например «BCBA». НОП лежит в основе сравнения файлов в diff и git и выравнивания последовательностей ДНК.
- L[i][j]длина НОП первых i символов a и первых j символов b
- L[0][j] = L[i][0]0 (с пустой строкой ничего общего нет)
Время O(m · n): для двух строк длины 1000 нужно всего 10⁶ ячеек, а перебор всех подпоследовательностей означал бы 2¹⁰⁰⁰ вариантов.
def lcs(a, b):
dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i in range(1, len(a) + 1):
for j in range(1, len(b) + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
out, i, j = [], len(a), len(b)
while i and j:
if a[i - 1] == b[j - 1]:
out.append(a[i - 1])
i, j = i - 1, j - 1
elif dp[i - 1][j] >= dp[i][j - 1]:
i -= 1
else:
j -= 1
return dp[-1][-1], ''.join(reversed(out))
print(lcs('ABCBDAB', 'BDCABA'))
print(lcs('AGGTAB', 'GXTXAYB'))▸ Ожидаемый результат
(4, 'BCBA') (4, 'GTAB')
Жадный алгоритм или ДП?
Жадный алгоритм на каждом шаге делает выбор, который кажется лучшим в данный момент, и никогда не возвращается назад. Он быстр и прост, но верен только для задач со «свойством жадного выбора»: Краскал, Дейкстра, кодирование Хаффмана, непрерывный (дробный) рюкзак. ДП же сравнивает все варианты без повторов и даёт верный ответ везде, где есть оптимальная подструктура и перекрывающиеся подзадачи.
- coins[x]наименьшее число монет для суммы x
- cдоступный номинал монеты
Монеты {1, 3, 4}, сумма 6. Сколько монет использует жадный алгоритм (всегда самая крупная монета)? Каков оптимум?
Показать решениеСкрыть решение
Таблица ДП coins[0 … 6]:
coins[1] = 1, coins[2] = 2, coins[3] = 1, coins[4] = 1,
coins[5] = 1 + min(coins[4], coins[2], coins[1]) = 1 + 1 = 2,
coins[6] = 1 + min(coins[5], coins[3], coins[2]) = 1 + 1 = 2.
Оптимум: 2 монеты (3 + 3). «Взять самую крупную» на первом шаге закрыло правильный путь.
def min_coins(coins, amount):
dp = [0] + [float('inf')] * amount
for x in range(1, amount + 1):
for c in coins:
if c <= x:
dp[x] = min(dp[x], dp[x - c] + 1)
return dp[amount], dp
def greedy_coins(coins, amount):
count = 0
for c in sorted(coins, reverse=True):
count += amount // c
amount %= c
return count
best, table = min_coins([1, 3, 4], 6)
print('greedy:', greedy_coins([1, 3, 4], 6), '| DP:', best, '| table:', table)
print('greedy:', greedy_coins([1, 5, 6, 9], 11), '| DP:', min_coins([1, 5, 6, 9], 11)[0])▸ Ожидаемый результат
greedy: 3 | DP: 2 | table: [0, 1, 2, 1, 1, 2, 2] greedy: 3 | DP: 2
| Подход | Идея | Когда верен | Пример |
|---|---|---|---|
| Разделяй и властвуй | независимые подзадачи | подзадачи не повторяются | сортировка слиянием |
| Динамическое программирование | запоминать ответы повторяющихся подзадач | оптимальная подструктура + перекрывающиеся подзадачи | рюкзак, НОП, монеты |
| Жадный | всегда локально лучший выбор | доказано свойство жадного выбора | Краскал, Дейкстра, Хаффман |
Главное
- Рекурсии нужны базовый случай и шаг, приближающий к нему; каждый вызов занимает кадр в стеке.
- Простой рекурсивный Фибоначчи — Θ(φⁿ), с мемоизацией или таблицей — O(n).
- Условия ДП: оптимальная подструктура и перекрывающиеся подзадачи; рецепт: состояние, переход, база, порядок.
- Рюкзак 0/1 — O(nW), НОП — O(mn); решение восстанавливается проходом по таблице назад.
- Жадный алгоритм быстр, но оптимален лишь при свойстве жадного выбора ({1, 3, 4} для 6: 2 монеты, а не 3).
Проверь себя
Вопросов: 10. Каждый правильный ответ приносит XP.