Динамическое программирование

⏱ 50 мин · 🧩 заданий: 7

Когда нужно ДП

Динамическое программирование — это способ решать задачу через ответы на её подзадачи, вычисляя каждую подзадачу один раз. Оно применимо, когда:

оптимальная подструктура — ответ собирается из ответов на меньшие подзадачи;
перекрывающиеся подзадачи — одни и те же подзадачи встречаются много раз.

Классический пример — числа Фибоначчи. Наивная рекурсия вычисляет одно и то же экспоненциально много раз:

calls = 0

def fib(n):
    global calls
    calls += 1
    return n if n < 2 else fib(n - 1) + fib(n - 2)

print(fib(25), "вызовов:", calls)

fib(5) / \ fib(4) fib(3) ← fib(3) считается дважды, / \ / \ fib(2) — трижды… fib(3) fib(2) fib(2) fib(1) / \ fib(2) fib(1)

Сверху вниз: рекурсия + кеш

Самый быстрый путь от рекурсивного решения к ДП — запомнить ответы. В Python это одна строка:

from functools import lru_cache

calls = 0

@lru_cache(maxsize=None)        # или @functools.cache
def fib(n):
    global calls
    calls += 1
    return n if n < 2 else fib(n - 1) + fib(n - 2)

print(fib(25), "вызовов:", calls)
print(fib(300))

Предел рекурсии

fib(5000) с кешем упадёт с RecursionError: глубина рекурсии ограничена (~1000). На собеседовании это повод сказать «перепишу снизу вверх».

Снизу вверх: таблица

Заполняем массив от базовых случаев к нужному ответу. Рекурсии нет, и часто хватает пары переменных вместо всей таблицы.

def fib_table(n):
    dp = [0, 1] + [0] * (n - 1)
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

def fib_fast(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(fib_table(50), fib_fast(50), len(str(fib_fast(5000))), "цифр")

Рецепт из пяти шагов

Состояние: что означает dp[i] (или dp[i][j])? Сформулируйте словами.
Переход: как dp[i] выражается через меньшие состояния?
База: значения для самых маленьких состояний.
Порядок: в каком порядке заполнять, чтобы нужные значения уже были посчитаны.
Ответ: какая ячейка (или максимум по каким ячейкам) — ответ.

Проговаривайте эти пять пунктов на собеседовании вслух — это лучше любой готовой формулы.

Лестница и уникальные пути

Лестница: сколько способов подняться на n ступенек, шагая на 1 или 2? Состояние dp[i] — число способов дойти до ступеньки i; переход dp[i] = dp[i-1] + dp[i-2]. Это снова Фибоначчи.

Уникальные пути в сетке m × n, шагая вправо или вниз: dp[r][c] = dp[r-1][c] + dp[r][c-1].

def climb(n):
    a, b = 1, 1
    for _ in range(n):
        a, b = b, a + b
    return a

def unique_paths(m, n, blocked=()):
    dp = [[0] * n for _ in range(m)]
    for r in range(m):
        for c in range(n):
            if (r, c) in blocked:
                continue
            if r == 0 and c == 0:
                dp[r][c] = 1
            else:
                dp[r][c] = (dp[r - 1][c] if r else 0) + (dp[r][c - 1] if c else 0)
    for row in dp:
        print(" ".join(f"{x:3}" for x in row))
    return dp[-1][-1]

print([climb(n) for n in range(1, 10)])
print("путей:", unique_paths(4, 5, blocked={(1, 1), (2, 3)}))

Размен монет

Состояние dp[s] — минимум монет для суммы s. Переход: перебрать последнюю монету c: dp[s] = min(dp[s - c] + 1).

def coin_change(coins, amount):
    INF = float("inf")
    dp = [0] + [INF] * amount
    for s in range(1, amount + 1):
        for c in coins:
            if c <= s:
                dp[s] = min(dp[s], dp[s - c] + 1)
    return dp

dp = coin_change([1, 3, 4], 10)
print(dp)
print("для 6:", dp[6], "— жадный взял бы 4+1+1")

Наибольшая возрастающая подпоследовательность

dp[i] — длина наибольшей возрастающей подпоследовательности, заканчивающейся в i. Это O(n²). Есть и O(n log n): храним tails[k] — минимальный возможный последний элемент возрастающей подпоследовательности длины k + 1 и обновляем его бинарным поиском.

from bisect import bisect_left

def lis_quadratic(nums):
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp, default=0)

def lis_fast(nums):
    tails = []
    for x in nums:
        i = bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
        print(f"{x:3} → tails = {tails}")
    return len(tails)

nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(lis_quadratic(nums))
print(lis_fast(nums))

Двумерное ДП на строках

Наибольшая общая подпоследовательность: dp[i][j] — ответ для префиксов a[:i] и b[:j]. Если последние символы равны, dp[i][j] = dp[i-1][j-1] + 1, иначе max(dp[i-1][j], dp[i][j-1]). Ту же таблицу можно пройти назад и восстановить саму подпоследовательность.

def lcs_table(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])
    # восстановление ответа
    i, j, chars = len(a), len(b), []
    while i and j:
        if a[i - 1] == b[j - 1]:
            chars.append(a[i - 1]); i -= 1; j -= 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return dp, "".join(reversed(chars))

a, b = "ABCBDAB", "BDCABA"
dp, s = lcs_table(a, b)
print("     " + "  ".join(b))
for i, row in enumerate(dp):
    print((" " + a)[i], row)
print("LCS:", s)

Редакционное расстояние устроено так же, только три перехода: удалить (dp[i-1][j] + 1), вставить (dp[i][j-1] + 1), заменить (dp[i-1][j-1] + (a[i-1] != b[j-1])). Им пользуются автокорректоры, difflib и поиск с опечатками.

Рюкзак 0/1

dp[c] — лучшая ценность при вместимости c. Для каждого предмета обходим вместимости с конца, чтобы не взять один предмет дважды. Если обходить с начала, получится «неограниченный рюкзак».

def knapsack(weights, values, capacity, unlimited=False):
    dp = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        order = range(w, capacity + 1) if unlimited else range(capacity, w - 1, -1)
        for c in order:
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[capacity]

print(knapsack([1, 3, 4], [15, 50, 60], 6))                    # 1 + 4 → 75
print(knapsack([1, 3, 4], [15, 50, 60], 6, unlimited=True))    # 3 + 3 → 100

Псевдополиномиальность

O(n · capacity) зависит от значения вместимости, а не от длины входа. При capacity = 10⁹ такое решение не подойдёт — это известная NP-трудная задача.

Как распознать ДП

Сигналы задачи на ДП

«Минимум/максимум», «сколько способов», «можно ли», и при этом решение складывается из решений для префиксов, подстрок, меньших сумм. Если перебор с возвратом повторно решает одни и те же подзадачи — добавьте кеш, и это уже ДП.

Начните с рекурсии + @cache, убедитесь, что ответ верный, затем при необходимости перепишите снизу вверх и сократите память до одной-двух строк таблицы.

Итог

ДП = подзадачи + запоминание. Сверху вниз — @cache, снизу вверх — таблица.
Рецепт: состояние, переход, база, порядок, ответ.
Одномерные: лестница, грабитель, монеты, LIS. Двумерные: LCS, Левенштейн, пути в сетке, рюкзак.
Память часто сокращается до O(n) или O(1).

Войдите, чтобы отмечать пройденные уроки.

	Динамическое программирование	Перебор с возвратом	Жадный алгоритм
Минимальное число монет для суммы при произвольных номиналах
Перечислить все перестановки строки
Максимум непересекающихся встреч в одной комнате
Число способов подняться на n ступенек по 1 или 2