Динамическое программирование: три шага, код на Python и разбор задач

Короткий ответ. Динамическое программирование это способ решать задачу через ответы на её меньшие версии. Ответ для n собирается из ответов для n - 1 и n - 2. Каждый маленький ответ считается один раз и запоминается. Так задачи «сколько способов», «минимальная стоимость», «максимальная выгода» решаются за O(n) или O(n²) вместо перебора. Ниже признаки, три шага, код на Python и разбор задач.

Что такое динамическое программирование?

Берём задачу, у которой большой ответ строится из маленьких. Определяем состояние: что именно значит «ответ для i». Пишем переход: как ответ для i получить из уже посчитанных.

Главное условие: маленькие задачи повторяются. Рекурсия без запоминания считала бы их снова и снова. Динамическое программирование считает каждую один раз.

Слово «динамическое» тут ничего не значит. Название историческое. Смысл в таблице ответов.

По каким словам в задаче узнать динамическое программирование?

• «Сколькими способами можно», «число путей».
• «Минимальная стоимость», «максимальная сумма без соседних».
• «Можно ли набрать сумму из монет», «можно ли разбить на два равных».
• «Самая длинная возрастающая подпоследовательность».

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

Из каких трёх шагов состоит решение?

• Состояние. dp[i] это ответ для первых i элементов или для числа i.
• Переход. Формула, которая выражает dp[i] через dp с меньшими индексами.
• База. Значения dp для самых маленьких i, которые известны сразу.

Потом остаётся порядок вычисления. Считаем от базы к нужному ответу. Тогда каждый переход ссылается на готовые ячейки.

Как это выглядит на примере?

Задача Climbing Stairs: лестница из n ступенек. Шаг на одну или на две. Сколько способов подняться?

Состояние: dp[i] это число способов дойти до ступеньки i. Переход: dp[i] = dp[i - 1] + dp[i - 2]. На ступеньку i приходят либо с i - 1, либо с i - 2. База: dp[1] = 1, dp[2] = 2.

Для n = 5: dp = [_, 1, 2, 3, 5, 8]. Ответ 8. Это числа Фибоначчи, и это не совпадение.

Как написать динамическое программирование на Python?

def climb_stairs(n):
    if n <= 2:
        return n
    a, b = 1, 2                      # dp[i-2], dp[i-1]
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b

def coin_change(coins, amount):
    INF = float("inf")
    dp = [0] + [INF] * amount        # dp[x] = минимум монет на сумму x
    for x in range(1, amount + 1):
        for c in coins:
            if c <= x and dp[x - c] + 1 < dp[x]:
                dp[x] = dp[x - c] + 1
    return -1 if dp[amount] == INF else dp[amount]

def rob(houses):
    take = skip = 0                  # лучший результат с последним взятым / пропущенным
    for h in houses:
        take, skip = skip + h, max(take, skip)
    return max(take, skip)

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

Чем восходящий способ отличается от нисходящего?

Признак	Снизу вверх (таблица)	Сверху вниз (мемоизация)
Форма кода	Цикл	Рекурсия с кешем
Порядок	Нужно выбрать самому	Рекурсия выберет сама
Память	Часто можно ужать до O(1)	Кеш плюс стек вызовов
Считает лишнее	Иногда все состояния	Только нужные
Риск	Ошибка в порядке	Переполнение стека

На собеседовании начинайте с рекурсии и кеша. Так проще найти переход. Потом переписывайте в цикл, если просят.

Как решить Coin Change?

Даны номиналы монет и сумма. Нужно минимальное число монет. Состояние: dp[x] это минимум монет на сумму x. Переход: для каждой монеты c пробуем dp[x - c] + 1. База: dp[0] = 0.

Жадный выбор самой большой монеты здесь ломается. Монеты [1, 3, 4], сумма 6. Жадность даёт 4 + 1 + 1, а ответ 3 + 3. Именно поэтому нужно динамическое программирование.

Как решить House Robber?

Ряд домов с деньгами. Нельзя брать два соседних. Нужна максимальная сумма.

Состояние: лучший результат для первых i домов. Переход: берём дом i и добавляем результат для i - 2. Или пропускаем и берём результат для i - 1. В коде выше это две переменные take и skip.

На каких ошибках ломается решение?

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

Как объяснить приём на собеседовании?

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

Сложность назовите как число состояний, умноженное на стоимость перехода. Для Coin Change это O(сумма · число монет).

Отработать узнавание приёма можно на странице динамическое программирование. Нисходящий вариант разобран на странице рекурсия с мемоизацией.

Вопросы и ответы

Как понять, что задача не на жадный алгоритм?

Найдите пример, где лучший локальный выбор портит итог. Монеты [1, 3, 4] и сумма 6 такой пример. Нашли, значит нужна таблица.

Сколько состояний может быть?

Обычно до нескольких миллионов. Если состояний больше, ищите другой параметр или другой приём.

Что делать, если нужен сам ответ, а не число?

Храните рядом с dp[i] выбор, который к нему привёл. В конце пройдите по выборам назад и соберите ответ.

Где динамическое программирование встречается в реальных системах?

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