Динамическое программирование: концепция и практические примеры

Введение

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

Концепция

Динамическое программирование применимо к задачам с двумя характерными свойствами: оптимальная подструктура (решение всей задачи может быть построено из оптимальных решений её подзадач) и перекрывающиеся подзадачи (одна и та же подзадача встречается многократно при наивном, рекурсивном решении без сохранения промежуточных результатов). Мемоизация (memoization, сверху-вниз) сохраняет результат каждой подзадачи при первом вычислении в кеше (обычно через хеш-таблицу или массив), и при повторном запросе той же подзадачи результат берётся из кеша вместо повторного вычисления — табуляция (снизу-вверх) достигает того же эффекта через явное, последовательное заполнение таблицы результатов подзадач от простейших случаев к более сложным, без рекурсии вовсе.

Пример кода

// Наивная рекурсивная реализация числа Фибоначчи — экспоненциальная сложность O(2^n)
// из-за многократного пересчёта ОДНИХ И ТЕХ ЖЕ подзадач (классическая демонстрация проблемы)
long long fibonacciNaive(int n)
{
    if (n <= 1) return n;
    return fibonacciNaive(n - 1) + fibonacciNaive(n - 2); // fibonacciNaive(n-2) пересчитывается
                                                             // МНОГОКРАТНО при разных путях рекурсии
}

// Мемоизация (сверху-вниз) — каждая подзадача вычисляется ровно ОДИН раз
#include <unordered_map>

long long fibonacciMemo(int n, std::unordered_map<int, long long> &cache)
{
    if (n <= 1) return n;
    if (cache.contains(n)) return cache[n]; // уже вычислено ранее — берём из кеша, O(1)

    long long result = fibonacciMemo(n - 1, cache) + fibonacciMemo(n - 2, cache);
    cache[n] = result; // сохраняем для возможного будущего запроса этой же подзадачи
    return result;
}
// Итоговая сложность — O(n), а не O(2^n) наивной версии

// Табуляция (снизу-вверх) — без рекурсии вовсе, последовательное заполнение таблицы
long long fibonacciTabulation(int n)
{
    if (n <= 1) return n;
    std::vector<long long> table(n + 1);
    table[0] = 0;
    table[1] = 1;
    for (int i = 2; i <= n; ++i) {
        table[i] = table[i - 1] + table[i - 2]; // каждое значение вычисляется ОДИН раз,
                                                   // используя уже готовые предыдущие значения
    }
    return table[n];
}

Пояснения к коду

fibonacciNaive демонстрирует проблему перекрывающихся подзадач явно — вызов fibonacciNaive(5) вызывает fibonacciNaive(3) дважды (через путь fibonacciNaive(4) и напрямую), и каждый из этих вызовов рекурсивно порождает собственное, полностью независимое, повторное дерево вызовов для одних и тех же, уже вычислявшихся ранее значений, что и приводит к экспоненциальному росту общего числа операций. fibonacciMemo решает эту проблему добавлением кеша (cache), проверяемого перед каждым потенциально повторным вычислением — это превращает экспоненциальную сложность в линейную ценой дополнительной памяти для хранения кеша. fibonacciTabulation достигает того же результата без рекурсии вовсе — явный, последовательный цикл заполняет таблицу результатов от простейших, базовых случаев к искомому n, что для многих задач ДП даёт дополнительное практическое преимущество избежания накладных расходов и риска переполнения стека рекурсивных вызовов.

Подводные камни

Применение мемоизации/динамического программирования к задаче без реальных перекрывающихся подзадач — если каждая подзадача в естественной рекурсивной декомпозиции задачи встречается ровно один раз (без повторения), кеширование не даёт никакой выгоды, лишь добавляя накладные расходы на работу с кешем без устранения какого-либо реального повторного вычисления; стоит явно проверить наличие перекрывающихся подзадач перед применением техники ДП, а не применять её «на всякий случай» для любой рекурсивной задачи.
Использование мемоизации с неэффективным или некорректным ключом кеша для подзадач, реально определяемых несколькими параметрами (а не единственным числом, как n в примере с Фибоначчи) — для многопараметрических подзадач нужен составной ключ кеша (например, std::pair или хеш-комбинация нескольких значений, аналогично подходу), и упущение какого-либо из реально значимых параметров в ключе кеша приведёт к некорректному, ошибочно «переиспользованному» результату для разных по сути подзадач, случайно получивших одинаковый, недостаточно специфичный ключ.
Неограниченный рост кеша мемоизации при большом числе различных подзадач, особенно при долгоживущем процессе, многократно решающем разные экземпляры похожей задачи без очистки кеша между ними — для таких случаев стоит явно продумать стратегию управления размером кеша (очистка, ограничение по размеру с вытеснением наименее недавно использованных записей), чтобы избежать неограниченного роста потребления памяти со временем.
Выбор табуляции для задачи, где реально нужна лишь небольшая часть всех возможных подзадач (а не вычисление для всех значений от простейшего случая до целевого, как в полном заполнении таблицы Фибоначчи) — для таких «разреженных» по реально нужным подзадачам случаев мемоизация (вычисляющая только реально запрошенные подзадачи) может быть эффективнее полной табуляции, вычисляющей результаты для абсолютно всех промежуточных случаев независимо от того, нужны ли они реально для конкретного итогового запроса.