Kodlo/eduplan-cpp-eltex
2
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
Files
main
eduplan-cpp-eltex/lessons/D5_algo.md
T

29 KiB
Raw Permalink Blame History

D5, часть 1. Динамическое программирование (урок)

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

1. Когда ДП вообще применимо

ДП применимо, если задача одновременно даёт два свойства:

  • Оптимальная подструктура — оптимальное решение всей задачи собирается из оптимальных решений подзадач (для LCS: если последние символы совпали, LCS всей строки — это LCS без последних символов плюс 1; оптимум подзадачи не пересчитывается заново).
  • Перекрывающиеся подзадачи — одни и те же подзадачи встречаются многократно при наивной рекурсии (для чисел Фибоначчи fib(5) вызывает fib(3) дважды, fib(2) трижды и так далее — без запоминания результат пересчитывается экспоненциально много раз).

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

Факты для карточек

  • base | Два условия применимости ДП? — оптимальная подструктура + перекрывающиеся подзадачи
  • core | Почему наивный рекурсивный fib(n) работает за экспоненциальное время? — одни и те же подзадачи (fib(k) для одного и того же k) пересчитываются заново много раз
  • core | Что ломается, если применить ДП-переход к задаче без оптимальной подструктуры? — переход не отражает реальную зависимость оптимумов, ответ будет неверным независимо от таблицы

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

2. Состояние, переход, мемоизация vs табуляция

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

Два способа посчитать одно и то же:

  • Мемоизация (top-down) — обычная рекурсия по формуле перехода, но перед вычислением проверяем кэш (unordered_map или массив), а после вычисления кладём результат в кэш. Считает только реально нужные состояния, но каждый вызов — это кадр стека.
  • Табуляция (bottom-up) — заполняем таблицу итеративно от базовых случаев к целевому, без рекурсии вообще. Требует явно определить порядок заполнения (что должно быть посчитано раньше, чем понадобится).
// мемоизация
long long fib_memo(int n, std::vector<long long>& cache) {
    if (n <= 1) return n;
    if (cache[n] != -1) return cache[n];
    return cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache);
}

// табуляция
long long fib_tab(int n) {
    std::vector<long long> dp(n + 1);
    dp[0] = 0; if (n >= 1) dp[1] = 1;
    for (int i = 2; i <= n; ++i) dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

Оба варианта — O(число состояний) по времени (каждое состояние считается ровно один раз, а не экспоненциально много) и O(число состояний) по памяти (нужно где-то хранить ответ для каждого состояния). У мемоизации есть дополнительный риск, которого нет у табуляции: рекурсия на входе с большим n (например, fib_memo(1'000'000, ...)) кладёт по кадру на каждый уровень — стек ограничен (типично несколько МБ), и глубокая рекурсия падает с переполнением стека (SIGSEGV) там, где итеративная табуляция отработает без проблем.

Ловушки

  • Забыть проверить кэш перед вычислением в мемоизации → рекурсия становится обычной наивной → возврат к экспоненциальному времени, видно по таймауту на больших n.
  • Взять слишком глубокую рекурсию для мемоизации (n порядка 10⁵–10⁶) → переполнение стека → падение по SIGSEGV, а не по логической ошибке.

Факты для карточек

  • base | Сложность по времени мемоизации/табуляции? — O(число состояний)
  • core | Чем мемоизация рискует, а табуляция — нет? — переполнением стека при большой глубине рекурсии
  • core | Что нужно определить в ДП-задаче до написания кода? — состояние (параметры подзадачи) и переход (формула через уже решённые состояния)

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

3. Уменьшение памяти: O(n) → O(1) или O(n)

Если переход использует только последние 1–2 строки/значения таблицы, всю таблицу хранить не нужно — достаточно «скользящего окна» из нужного числа последних значений.

Лестница (Climbing Stairs: сколько способов подняться на n ступеней шагами по 1 или 2): переход dp[i] = dp[i-1] + dp[i-2] использует только два предыдущих значения — O(1) памяти.

int climb_stairs(int n) {              // способов дойти до ступени n
    if (n <= 2) return n;
    int prev2 = 1, prev1 = 2;
    for (int i = 3; i <= n; ++i) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;                      // O(n) время, O(1) память
}

House Robber (нельзя грабить два соседних дома подряд, максимизировать сумму): тот же приём. dp[i] = max(dp[i-1], dp[i-2] + nums[i]) — не ограбить дом i (взять лучший результат без него) или ограбить (взять лучший результат через один плюс текущий дом).

int rob(const std::vector<int>& nums) {
    int prev2 = 0, prev1 = 0;
    for (int x : nums) {
        int curr = std::max(prev1, prev2 + x);
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;                      // O(n) время, O(1) память
}

Рюкзак 0/1 ужимается не до O(1), а до O(W) (одна строка по весу вместо таблицы n×W) — переход там зависит от целой предыдущей строки, а не от 1–2 чисел; подробно в следующем разделе.

Факты для карточек

  • base | Сложность по памяти Climbing Stairs при развёрнутых prev1/prev2? — O(1)
  • core | Почему рюкзак 0/1 нельзя ужать до O(1), только до O(W)? — переход dp[i][w] зависит от целой предыдущей строки по весу, а не от 1–2 соседних чисел

Почему дальше: рюкзак — задача, где переход по весу нельзя писать «вперёд» без потери корректности; разберём, почему именно назад.

4. Рюкзак 0/1: почему обратный проход по весу

Задача: n предметов с весом weight[i] и ценностью value[i], вместимость W, каждый предмет берётся не более одного раза, максимизировать суммарную ценность.

int knapsack01(const std::vector<int>& weight, const std::vector<int>& value, int W) {
    std::vector<int> dp(W + 1, 0);
    for (size_t i = 0; i < weight.size(); ++i)
        for (int w = W; w >= weight[i]; --w)     // обратный проход!
            dp[w] = std::max(dp[w], dp[w - weight[i]] + value[i]);
    return dp[W];                                // O(n·W) время, O(W) память
}

Если одномерный массив dp[w] переиспользуется для всех предметов подряд (без второго измерения по номеру предмета), то при проходе весов вперёд (w от weight[i] до W) значение dp[w - weight[i]], использованное в переходе, могло уже быть обновлено этим же предметом i на текущей итерации — то есть предмет i фактически используется дважды, и задача незаметно превращается в рюкзак с неограниченным числом копий предмета (unbounded knapsack). Проход назад гарантирует, что dp[w - weight[i]] берётся из состояния «до предмета i» — старое значение ещё не тронуто текущей итерацией внешнего цикла.

Ловушки

  • Пройти веса вперёд в одномерном 0/1-рюкзаке → предмет учитывается несколько раз → ответ завышен относительно эталона, видно на тесте с одним дорогим предметом.
  • Перепутать размер массива (W вместо W+1) → индекс dp[W] вне границ → UB/ASAN heap-buffer-overflow.

Факты для карточек

  • base | Временная сложность 0/1-рюкзака с одномерным массивом? — O(n·W)
  • core | Почему в одномерном 0/1-рюкзаке веса обходят от W к weight[i], а не наоборот? — иначе dp[w-weight[i]] уже обновлён текущим предметом в этой же итерации, предмет посчитается дважды
  • deep | Как называется вариант рюкзака, в который случайно превращается 0/1-рюкзак при прямом проходе весов? — unbounded knapsack (неограниченное число копий предмета)

Почему дальше: та же ловушка с порядком циклов — не по направлению, а по тому, что снаружи, а что внутри — по-другому проявляется в задаче про размен монет.

5. Монеты: порядок циклов меняет смысл ответа

Coin Change (минимальное число монет для суммы amount, каждая монета берётся неограниченное число раз — это уже unbounded knapsack):

int coin_change(const std::vector<int>& coins, int amount) {
    std::vector<int> dp(amount + 1, INT_MAX);
    dp[0] = 0;
    for (int a = 1; a <= amount; ++a)
        for (int c : coins)
            if (c <= a && dp[a - c] != INT_MAX)
                dp[a] = std::min(dp[a], dp[a - c] + 1);
    return dp[amount] == INT_MAX ? -1 : dp[amount];   // O(amount · coins.size())
}

Для минимума порядок циклов не влияет на корректность — минимум не зависит от того, в каком порядке предметы разрешено переиспользовать. Но для подсчёта числа способов (Coin Change II) порядок циклов меняет сам смысл ответа:

// количество КОМБИНАЦИЙ: {1,2} и {2,1} — один и тот же способ
long long change_combinations(int amount, const std::vector<int>& coins) {
    std::vector<long long> dp(amount + 1, 0);
    dp[0] = 1;
    for (int c : coins)                    // внешний цикл — монета
        for (int a = c; a <= amount; ++a)
            dp[a] += dp[a - c];
    return dp[amount];
}

// количество ПЕРЕСТАНОВОК: {1,2} и {2,1} — разные способы
long long change_permutations(int amount, const std::vector<int>& coins) {
    std::vector<long long> dp(amount + 1, 0);
    dp[0] = 1;
    for (int a = 1; a <= amount; ++a)      // внешний цикл — сумма
        for (int c : coins)
            if (c <= a) dp[a] += dp[a - c];
    return dp[amount];
}

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

Ловушки

  • Перепутать порядок циклов в задаче «сколько способов» → вместо количества комбинаций получается количество перестановок (число сильно больше ожидаемого) → расходится с эталонным ответом на тесте с 2+ разными монетами.

Факты для карточек

  • base | Сложность Coin Change (минимум монет) по времени? — O(amount · число_номиналов)
  • core | Какой порядок циклов в Coin Change II даёт число комбинаций, а какой — перестановок? — монета снаружи/сумма внутри → комбинации; сумма снаружи/монета внутри → перестановки

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

6. LCS и Edit Distance: таблица (n+1)×(m+1)

LCS (длиннейшая общая подпоследовательность двух строк, не обязательно непрерывная):

int lcs_length(const std::string& a, const std::string& b) {
    int n = a.size(), m = b.size();
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1, 0));
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            dp[i][j] = (a[i - 1] == b[j - 1])
                ? dp[i - 1][j - 1] + 1
                : std::max(dp[i - 1][j], dp[i][j - 1]);
    return dp[n][m];                    // O(n·m) время и память
}

Строка 0 и столбец 0 — базовый случай «одна из строк пустая», отсюда размер (n+1)×(m+1), а не n×m. Если последние символы совпадают, они точно входят в оптимальную LCS — переход к dp[i-1][j-1]+1. Если нет — общая подпоследовательность не может использовать оба последних символа одновременно, берём лучшее из «отбросить последний символ a» и «отбросить последний символ b».

Edit Distance (минимум вставок/удалений/замен, чтобы превратить строку a в b):

int edit_distance(const std::string& a, const std::string& b) {
    int n = a.size(), m = b.size();
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1));
    for (int i = 0; i <= n; ++i) dp[i][0] = i;   // удалить все i символов
    for (int j = 0; j <= m; ++j) dp[0][j] = j;   // вставить все j символов
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            dp[i][j] = (a[i - 1] == b[j - 1])
                ? dp[i - 1][j - 1]
                : 1 + std::min({dp[i - 1][j - 1],   // замена
                                 dp[i - 1][j],        // удаление
                                 dp[i][j - 1]});      // вставка
    return dp[n][m];                     // O(n·m) время и память
}

Тот же размер таблицы (n+1)×(m+1) и та же причина: строка/столбец 0 — превращение пустой строки в префикс другой строки чисто вставками или удалениями.

Ловушки

  • Завести таблицу n×m вместо (n+1)×(m+1) → нет места для базового случая «пустой префикс» → неверные значения на границе или выход за границы массива.
  • В Edit Distance забыть инициализировать нулевую строку/столбец → сравнение с мусорными значениями → неверный ответ без падения программы (тихая ошибка).

Факты для карточек

  • base | Размер таблицы LCS/Edit Distance для строк длины n и m? — (n+1)×(m+1)
  • base | Временная сложность LCS и Edit Distance? — O(n·m)
  • core | Почему при несовпадении последних символов в LCS берут max(dp[i-1][j], dp[i][j-1])? — оба последних символа одновременно в общую подпоследовательность войти не могут, значит хотя бы один из них можно отбросить без потери оптимальности

Почему дальше: LCS/Edit Distance решают за O(n·m) через явную таблицу. Следующая классическая задача — LIS — решается за O(n²) той же схемой, но улучшается до O(n log n) совсем другим приёмом.

7. LIS (НВП): O(n²) и O(n log n)

Длиннейшая строго возрастающая подпоследовательность массива (не обязательно непрерывная). Сигнатура из tasks/05_lis: int lis_length(const std::vector<int>& a).

Наивное O(n²): dp[i] — длина LIS, заканчивающейся ровно на элементе a[i].

int lis_naive(const std::vector<int>& a) {
    int n = a.size();
    std::vector<int> dp(n, 1);
    int best = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j)
            if (a[j] < a[i]) dp[i] = std::max(dp[i], dp[j] + 1);
        best = std::max(best, dp[i]);
    }
    return best;                        // O(n²)
}

На 100 000 элементах (ограничение задачи 05_lis) это 10¹⁰ операций — не укладывается в 2 секунды внутреннего теста, нужен другой алгоритм.

O(n log n) через массив «хвостов»:

int lis_length(const std::vector<int>& a) {
    std::vector<int> tails;               // tails[k] = минимальный возможный последний
                                           // элемент возрастающей подпоследовательности длины k+1
    for (int x : a) {
        auto it = std::lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);   // x больше всех хвостов — новая длина
        else *it = x;                                 // заменить первый хвост ≥ x на x
    }
    return tails.size();                  // O(n log n)
}

tails не хранит саму подпоследовательность — только минимально возможное значение последнего элемента для каждой достижимой длины. tails всегда отсортирован по построению: если x заменяет элемент на позиции it, новое значение x меньше старого (иначе lower_bound нашёл бы другую позицию) и больше всех элементов слева от it (иначе lower_bound остановился бы раньше) — порядок не нарушается ни при замене, ни при добавлении в конец. lower_bound ищет первый элемент ≥ x, что даёт строго возрастающую LIS (task.md требует именно строгую); для нестрогой (неубывающей) подпоследовательности нужен upper_bound. Длина tails в конце равна длине LIS, хотя сам массив LIS обычно не является.

Факты для карточек

  • base | Наивная сложность LIS через dp[i]? — O(n²)
  • base | Сложность LIS через массив хвостов и бинарный поиск? — O(n log n)
  • core | Что хранится в tails[k]? — минимально возможный последний элемент возрастающей подпоследовательности длины k+1
  • core | Почему tails остаётся отсортированным после каждой замены/добавления? — новое значение всегда меньше заменяемого и больше всех элементов левее позиции, найденной lower_bound
  • core | lower_bound или upper_bound нужен для строго возрастающей LIS? — lower_bound
  • deep | Сколько операций у наивного O(n²) LIS на 100 000 элементах и почему это не укладывается в тест? — порядка 10¹⁰, тест роняет прогон при времени > 2 с

Почему дальше: LIS через хвосты — пример, где ДП-таблица заменяется одним отсортированным массивом и бинарным поиском; та же идея (жертвовать явной таблицей ради log-фактора) встречается и в других задачах на подпоследовательности.

Ссылки на задачи этого дня: tasks/05_lis — реализовать lis_length за O(n log n); наивная O(n²) версия не пройдёт по времени на 100 000 элементах.

Проверь себя

  1. Массив весов [1, 3, 4], ценностей [15, 20, 30], вместимость W=4. Какой ответ даст 0/1-рюкзак и почему это не «взять предметы 1 и 2» (вес 1+3=4)?

    Ответ35 — рюкзак действительно может выбрать предметы с весами 1 и 3 (суммарный вес 4, ценность 15+20=35); предмет весом 4 отдельно даёт только 30, что меньше. Ответ 35, а не 30 — если получилось 30, значит в переборе не сравнили оба варианта заполнения веса 4.

  2. Почему для Coin Change II (подсчёт числа способов, не минимума) важно, какой цикл снаружи — монета или сумма, — а для Coin Change (минимум монет) не важно?

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

  3. Для массива [3, 1, 4, 1, 5, 9, 2, 6] пройдите LIS через tails вручную. Чему равен tails после обработки первых пяти элементов (3, 1, 4, 1, 5)?

    Ответ`[1, 4, 5]`: 3 → `[3]`; 1 заменяет 3 → `[1]`; 4 больше всех → `[1,4]`; 1 заменяет первый элемент ≥1 (сам 1) → `[1,4]` без изменений; 5 больше всех → `[1,4,5]`.

  4. Мемоизация fib_memo(n, cache) вызвана с n = 200 000. Почему это скорее упадёт по SIGSEGV, чем отработает медленно?

    ОтветКаждый рекурсивный вызов держит кадр стека, пока не вернётся его результат; глубина рекурсии здесь равна n, а размер стека потока ограничен (типично несколько МБ) — при n=200 000 кадров стек переполняется раньше, чем вычисление успевает завершиться. Табуляция (`fib_tab`) того же n отработает без проблем — там нет рекурсии, только цикл.

Материалы

Reference in New Issue View Git Blame Copy Permalink