Блок «Алгоритмы на строках» закончился задачами на КМП, Z-функцию и палиндромы. Теперь начинается новый блок — динамическое программирование. Это одна из самых весомых тем технических интервью и олимпиад: по статистике LeetCode, задачи на DP составляют около 25% вопросов уровня Medium и больше половины Hard. За внушительным названием скрываются два конкретных приёма, которые вы освоите в этом уроке. Что такое динамическое программирование**

Динамическое программирование — это техника, которая применяется к задачам с двумя свойствами. Первое — оптимальная подструктура (optimal substructure): оптимальное решение задачи можно выразить через оптимальные решения её подзадач. Второе — перекрывающиеся подзадачи (overlapping subproblems): одни и те же подзадачи встречаются снова и снова при рекурсивном разложении.

Если выполнено только первое свойство — часто достаточно жадного алгоритма или «разделяй и властвуй». Бинарный поиск, например, делит задачу на подзадачи, но никогда не решает одну и ту же дважды: каждый следующий шаг работает с принципиально новыми данными. Сортировка слиянием аналогично делит массив без перекрытий. DP нужен именно тогда, когда рекурсия повторяет одну и ту же работу многократно — и мы хотим эту работу сохранить.

Перед тем как смотреть на код — аналогия. Представьте, что вы переводчик и работаете с книгой. Какое-то редкое слово встречается двести раз. Если каждый раз лезть в словарь — теряете массу времени. Если записать перевод на стикер и приклеить рядом — один раз нашли, двести раз использовали. DP — это «стикер для подзадач».

Разберём на классическом примере — числе Фибоначчи. F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) для n >= 2. Наивная рекурсия кодирует определение напрямую:

int FibNaive(int n)
{
    if (n <= 1) return n;
    return FibNaive(n - 1) + FibNaive(n - 2);
}

Console.WriteLine(FibNaive(10));  // 55 — быстро
Console.WriteLine(FibNaive(40));  // 102334155 — несколько секунд
// FibNaive(50) — минуты; FibNaive(100) — больше возраста Вселенной

Почему так медленно? Нарисуйте дерево вызовов для F(6). Чтобы вычислить F(6), нужны F(5) и F(4). Чтобы вычислить F(5) — нужны F(4) и F(3). F(4) вызывается уже дважды. F(3) — трижды. F(2) — пять раз. Общее число вызовов при FibNaive(n) растёт как O(2^n): при n = 50 это больше квадриллиона рекурсивных обращений. Алгоритм правильный, но безмерно расточительный.

Ключевое наблюдение: одна и та же подзадача FibNaive(k) вычисляется из раза в раз, всегда давая один и тот же ответ. Это и есть перекрывающиеся подзадачи. Если бы каждая подзадача встречалась только один раз — рекурсия работала бы нормально. Но здесь — встречаются экспоненциальное число раз. Подход 1: мемоизация (top-down)**

Мемоизация — это та же рекурсия, но с кешем. Перед тем как начать считать F(n), проверяем: нет ли уже готового ответа в словаре? Если есть — возвращаем немедленно. Если нет — вычисляем, сохраняем, возвращаем.

// Мемоизация через Dictionary<int, long>
static Dictionary<int, long> _memo = new Dictionary<int, long>();

static long FibMemo(int n)
{
    if (n <= 1) return n;

    // Проверяем кеш — TryGetValue быстрее, чем ContainsKey + индексер
    if (_memo.TryGetValue(n, out long cached))
        return cached;

    // Ничего не нашли — считаем и сохраняем
    long result = FibMemo(n - 1) + FibMemo(n - 2);
    _memo[n] = result;
    return result;
}

Console.WriteLine(FibMemo(10));  // 55
Console.WriteLine(FibMemo(50));  // 12586269025 — мгновенно
Console.WriteLine(FibMemo(90));  // 2880067194370816120

Что изменилось принципиально? Теперь каждое значение F(k) вычисляется ровно один раз, а потом берётся из словаря за O(1). Дерево вызовов из разросшегося куста превращается в прямую цепочку: сначала рекурсия уходит вглубь до F(0), потом каждое значение вычисляется при подъёме — ровно один раз. Итоговая сложность: O(n) по времени и O(n) по памяти (словарь хранит n значений).

Название «сверху вниз» (top-down) описывает направление: мы начинаем с большой задачи F(n) и рекурсивно спускаемся к маленьким. Код сохраняет форму оригинальной рекурсии — изменений минимум. Это большое практическое преимущество: когда вы уже написали правильную, но медленную рекурсию, добавить мемоизацию можно за три строки.

В C# для плотных целочисленных ключей массив работает быстрее словаря примерно в 2-5 раз:

static long[] _cache;

static long FibMemoArray(int n)
{
    _cache = new long[n + 1];
    Array.Fill(_cache, -1L); // -1 означает «ещё не посчитано»
    return Solve(n);
}

static long Solve(int n)
{
    if (n <= 1) return n;
    if (_cache[n] != -1L) return _cache[n]; // в кеше есть — берём

    _cache[n] = Solve(n - 1) + Solve(n - 2);
    return _cache[n];
}

Массив требует знать максимальное n заранее. Словарь гибче: когда ключи — строки, пары (int, int), кортежи или разреженные числа — словарь незаменим. В задачах на строках (поиск подпоследовательности, редакционное расстояние) ключ подзадачи — пара индексов (i, j), и Dictionary<(int, int), int> описывает это естественно.

Важный подводный камень мемоизации: глубина рекурсии в .NET ограничена. При n = 10 000 рекурсивный вызов вглубь до FibMemo(0) создаст стек из 10 000 фреймов. По умолчанию стек .NET-потока позволяет примерно 500-1000 рекурсивных вызовов до StackOverflowException. Таблирование этой проблемы лишено полностью.

Подход 2: таблирование (bottom-up)

Таблирование — итеративный подход «снизу вверх» (bottom-up): начинаем с базовых случаев и последовательно заполняем таблицу, пока не дойдём до нужного значения. Никакой рекурсии, никакого стека вызовов.

static long FibTab(int n)
{
    if (n <= 1) return n;

    long[] dp = new long[n + 1];
    dp[0] = 0; // база 1
    dp[1] = 1; // база 2

    // Заполняем слева направо — каждый dp[i] зависит только от уже готовых
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];

    return dp[n];
}

Console.WriteLine(FibTab(10));  // 55
Console.WriteLine(FibTab(50));  // 12586269025

Результат идентичен мемоизации — O(n) время, O(n) память. Преимущества таблирования: нет глубокой рекурсии (нет риска StackOverflowException), проще отлаживать (можно распечатать массив dp и увидеть, как растут значения), чуть быстрее на практике (нет накладных расходов на вызовы функций и проверки кеша).

Порядок заполнения таблицы имеет значение. В примере выше мы заполняем dp слева направо, потому что dp[i] зависит от dp[i-1] и dp[i-2] — то есть от уже готовых значений. Если бы зависимость шла вправо (dp[i] зависит от dp[i+1]), мы бы заполняли справа налево. Правило: заполняй в том порядке, в котором зависимости уже вычислены.

Оптимизация памяти до O(1)

В задаче Фибоначчи dp[i] зависит только от двух предыдущих значений. Зачем хранить весь массив длиной n+1, если нам нужны только последние два элемента? Достаточно двух переменных.

static long FibOptimal(int n)
{
    if (n <= 1) return n;

    long prev2 = 0; // F(n-2): начинаем с F(0)
    long prev1 = 1; // F(n-1): начинаем с F(1)

    for (int i = 2; i <= n; i++)
    {
        long current = prev1 + prev2; // F(i) = F(i-1) + F(i-2)
        prev2 = prev1;                // сдвигаем окно вправо
        prev1 = current;
    }

    return prev1; // prev1 теперь хранит F(n)
}

Console.WriteLine(FibOptimal(10));  // 55
Console.WriteLine(FibOptimal(90));  // 2880067194370816120

Это стандартная оптимизация таблирования: если рекуррентное соотношение dp[i] зависит только от dp[i-1] и dp[i-2], можно хранить только «окно» из двух значений. В более сложных задачах окно может быть шире: dp[i] зависит от dp[i-1], dp[i-2], dp[i-3] — тогда храним три переменные. Принцип тот же.

Итоговое сравнение четырёх вариантов для числа Фибоначчи:

Наивная рекурсия: время O(2^n), память O(n) (стек), допустима только при n не больше 30-35. Мемоизация (Dictionary): время O(n), память O(n), удобна при сложных ключах, риск переполнения стека при больших n. Таблирование (массив): время O(n), память O(n), нет риска стека, легко отлаживать. Оптимизированное таблирование: время O(n), память O(1), лучший выбор для больших n.

Когда выбирать мемоизацию, а когда таблирование**

На практике оба подхода дают одинаковую асимптотику. Выбор зависит от структуры задачи и контекста.

Мемоизация лучше подходит, когда пространство подзадач разреженное — вы вычислите лишь небольшую их часть. Например, в задаче поиска пути в графе с большим количеством состояний рекурсия с мемоизацией не тронет недостижимые состояния вовсе, а таблирование заполнит их «по умолчанию» нулями. Мемоизация также удобна, когда рекурсивная структура задачи читается легко — код выглядит почти как математическое определение. И особенно хороша при сложных ключах: строках, парах чисел, множествах.

Таблирование лучше подходит, когда пространство подзадач плотное (вы всё равно посчитаете большинство из них), когда рекурсия слишком глубокая и угрожает переполнением стека, или когда нужна оптимизация памяти — убрать «лишние» строки таблицы в итеративном коде проще, чем в рекурсивном.

Оба подхода требуют одного и того же ключевого навыка: правильно определить подзадачу, сформулировать рекуррентное соотношение и установить базовые случаи. Это единственное, что реально сложно в DP. Сам механизм кеша (мемоизация) или заполнения таблицы (таблирование) — технические детали, которые пишутся почти автоматически.

Хороший способ научиться: для каждой DP-задачи сначала напишите наивную рекурсию, убедитесь что она правильная, потом добавьте кеш (мемоизация) и убедитесь что ответ не изменился, потом переведите в таблирование. Три шага, три версии кода, нарастающий контроль.

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

Ещё одна полезная привычка: перед тем как писать код, проговорите вслух (или на бумаге) — что означает dp[i]? Что означает dp[i][j]? Если вы не можете чётко сформулировать смысл ячейки таблицы, код скорее всего будет неверным. «dp[i] — максимальная ценность при использовании первых i предметов» — это чёткое определение. «dp[i] — что-то про предметы» — нет.