Перебор, ДП и жадные алгоритмы

Рекурсия и дерево вызовов

def fib(n):
    if n < 2:        # база
        return n
    return fib(n - 1) + fib(n - 2)

• Время — число узлов дерева, память — его глубина: на стеке живёт только текущая ветка.
• Два вызова на уровень — дерево растёт как φⁿ ≈ 1,6ⁿ. Причина — одни и те же подзадачи считаются снова и снова.
• Запомнить ответ подзадачи — мемоизация. Дерево схлопывается в цепочку из 2n−1 вызовов.

Глубина ограничена стеком: Python — 1000 кадров (RecursionError), Node — ~10 тыс. (RangeError), Java — размер -Xss, Go растит стек горутины до 1 ГБ. Подробнее — в «Стек и куча».

Сверху вниз и снизу вверх

from functools import cache

@cache              # сверху вниз
def ways(n):
    if n <= 1:
        return 1
    return ways(n - 1) + ways(n - 2)

def ways_table(n):  # снизу вверх
    a, b = 1, 1     # dp[i-2], dp[i-1]
    for _ in range(n - 1):
        a, b = b, a + b
    return b

«Сколькими способами подняться на n ступенек шагами по 1 и 2?» Последний шаг — либо 1, либо 2, поэтому dp[i] = dp[i−1] + dp[i−2]. Таблица считает подзадачи в правильном порядке без рекурсии и стека, а когда нужны только две последние — хватает двух переменных.

Перебор с возвратом

def backtrack(state):
    if is_solution(state):
        yield list(state)
    for choice in choices(state):
        if not valid(state, choice):
            continue              # отсечение
        state.append(choice)      # вперёд
        yield from backtrack(state)
        state.pop()               # назад

Шаблон для «перечислить все»: подмножества, перестановки, сочетания с суммой, судоку, поиск слова в сетке. Ответов экспоненциально много — выигрыш только в отсечении: чем раньше видно, что ветка тупиковая, тем меньше дерево. Так же работают SAT-солверы и планировщики расписаний.

Редакционное расстояние

Сколько вставок, удалений и замен превращают одно слово в другое (Левенштейн). dp[i][j] — расстояние между первыми i буквами одного слова и j буквами другого. Буквы совпали — берём диагональ, иначе 1 + минимум из трёх соседей.

• Проверка орфографии и «Возможно, вы имели в виду…»; levenshtein() в Postgres (fuzzystrmatch).
• Нечёткий поиск Elasticsearch (fuzziness: AUTO) — до 2 правок, через автомат Левенштейна, а не таблицу на каждый терм.
• difflib.get_close_matches в Python считает другую меру — Ратклиффа — Обершелпа. Для Левенштейна берут rapidfuzz.

Как работает diff

Diff двух файлов — это наибольшая общая подпоследовательность строк (LCS): что в неё вошло, остаётся без изменений, остальное — «−» и «+». Таблица та же, что у Левенштейна, только без замен.

• Таблица — O(n·m): два файла по 100 тыс. строк — 10¹⁰ клеток. Поэтому GNU diff и git используют алгоритм Майерса: O((n+m)·D), где D — число отличий. Похожие файлы сравниваются почти линейно.
• git diff --patience и --histogram сначала сопоставляют уникальные строки — дифф получается понятнее, когда в коде много одинаковых }.

Рюкзак 0/1

Есть предметы с весом и ценностью и рюкзак вместимостью W. Каждый предмет берём целиком или не берём. dp[i][w] — лучшая ценность из первых i предметов при вместимости w:

dp[i][w] = max(dp[i-1][w],                        # не берём
               dp[i-1][w - wt[i]] + val[i])       # берём

O(n·W) — «псевдополиномиально»: зависит от величины W, а не от длины входа. Вместимость 10⁹ так не решить. В жизни это бюджет: какие задачи взять в спринт, какие объекты держать в кэше, какие рекламные блоки поставить в слот. Жадный выбор по «ценности за килограмм» здесь ошибается.

Размен монет: жадно или ДП

Набрать сумму минимальным числом монет. Жадно — брать самую крупную монету, которая помещается. Для рублей, евро и долларов это оптимально: такие системы называют каноническими. Для произвольных номиналов — нет.

from math import 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)

Та же таблица отвечает на три вопроса: «минимум монет» (min), «сколькими способами» (+=, цикл по монетам снаружи) и «можно ли набрать вообще» (or).

Самая длинная возрастающая цепочка (LIS)

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

from bisect import bisect_left
tails = []
for x in a:
    k = bisect_left(tails, x)
    if k == len(tails): tails.append(x)
    else:               tails[k] = x
return len(tails)

Это «пасьянс»: карты раскладывают в стопки. Отсюда patience diff — LIS по номерам уникальных общих строк двух файлов.

Жадные алгоритмы: когда выбор доказуемо верен

Жадный алгоритм делает локально лучший шаг и никогда его не пересматривает. Это верно, только если доказано: любое оптимальное решение можно переделать так, чтобы оно начиналось с жадного шага (аргумент обмена).

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

Код Хаффмана

Частым символам — короткие коды, редким — длинные. Жадно: дважды достать из кучи два самых редких узла и склеить их в один. Получается оптимальный префиксный код: ни один код не начало другого, поэтому разделители не нужны.

• DEFLATE — gzip, zlib, PNG, zip, HTTP Content-Encoding: gzip: сначала LZ77 заменяет повторы ссылками, потом Хаффман кодирует результат.
• HPACK в HTTP/2 сжимает заголовки статическим кодом Хаффмана; JPEG, Brotli и zstd тоже используют префиксные коды.
• Дейкстра — тоже жадный алгоритм: берёт ближайшую непосещённую вершину. Подробнее — в презентации про графы.

Перенос строк: жадно против ДП

Жадный перенос кладёт в строку столько слов, сколько влезает. ДП выбирает разбиение всего абзаца: dp[i] — минимальная цена текста с i-го слова до конца, переход — где закончить первую строку.

Цена строки — квадрат пустого места справа (последняя строка бесплатна). Квадрат штрафует одну очень пустую строку сильнее, чем несколько чуть неполных. Это задача Text Justification с LeetCode и упрощённая версия того, что делает TeX.

Как узнать задачу на собеседовании

• «Сколькими способами», «минимальная/максимальная стоимость», «можно ли достичь» — почти всегда ДП.
• «Перечислите все», «найдите любую расстановку» — перебор с возвратом.
• Интервалы, расписание, «минимум операций» с очевидным лучшим шагом — жадный алгоритм после сортировки. Сначала поищите контрпример.
• Ограничения подсказывают сложность: n ≤ 10 — n!, n ≤ 20 — 2ⁿ (маски), n ≤ 5000 — O(n²), n ≤ 10⁵ — O(n log n).

Порядок ответа: перебор → «вот повторяющиеся подзадачи» → мемоизация → таблица → экономия памяти. Каждый шаг проговаривайте.