Введение в DP

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

Динамическое программирование, или DP, — это метод решения задач, где большая задача разбивается на маленькие подзадачи.

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

большая задача
↓
маленькие подзадачи
↓
сохраняем ответы
↓
получаем ответ на всю задачу

DP часто начинается с рекурсии. Потом рекурсию можно перевести в итеративный метод через массив dp.

Когда использовать DP?

задача разбивается на одинаковые подзадачи
одни и те же значения считаются много раз
нужно найти максимум или минимум
нужно посчитать количество способов
есть переход из меньшего состояния в большее
можно придумать состояние dp

Главная идея DP

В DP мы обычно придумываем массив:

dp[i]

Это ответ для маленькой задачи номер i.

Например:

dp[i] = ответ для первых i элементов
dp[i] = количество способов дойти до i
dp[i] = минимальная стоимость до i
dp[i] = максимальная сумма до i

Рекурсивный метод

Сначала задачу удобно думать через рекурсию.

Мы пишем функцию:

f(i)

Она возвращает ответ для состояния i.

f(i) = ответ для задачи i

Потом выражаем f(i) через меньшие значения:

f(i) = f(i - 1) + f(i - 2)

Это называется переход.

Пример: числа Фибоначчи

Числа Фибоначчи:

f(0) = 0
f(1) = 1
f(n) = f(n - 1) + f(n - 2)

То есть каждое число равно сумме двух предыдущих.

Обычная рекурсия

int fib(int n) {
    if (n == 0) {
        return 0;
    }

    if (n == 1) {
        return 1;
    }

    return fib(n - 1) + fib(n - 2);
}

Этот код правильный, но очень медленный.

Почему?

fib(5)
вызывает fib(4) и fib(3)
fib(4) снова вызывает fib(3)
одно и то же fib(3) считается несколько раз

Проблема обычной рекурсии

Обычная рекурсия много раз считает одинаковые состояния.

Например:

fib(6)
fib(5) + fib(4)
fib(4) считается несколько раз
fib(3) считается еще больше раз

Из-за повторных вычислений обычная рекурсия для Фибоначчи работает примерно за O(2ⁿ).

Рекурсия + мемоизация

Чтобы не считать одно и то же много раз, сохраняем ответы в массиве.

int dp[N];

Если dp[n] уже посчитан, просто возвращаем его.

if (dp[n] != -1) {
    return dp[n];
}

Такой метод называется мемоизация.

Фибоначчи через мемоизацию

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int dp[N];

int fib(int n) {
    if (n == 0) {
        return 0;
    }

    if (n == 1) {
        return 1;
    }

    if (dp[n] != -1) {
        return dp[n];
    }

    dp[n] = fib(n - 1) + fib(n - 2);
    return dp[n];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    for (int i = 0; i < N; i++) {
        dp[i] = -1;
    }

    cout << fib(n);

    return 0;
}

Что изменилось?

Теперь каждое значение fib(i) считается только один раз.

fib(5) посчитали → сохранили в dp[5]
если снова нужен fib(5), просто берем dp[5]

Поэтому сложность стала:

Метод	Время	Память
Обычная рекурсия	O(2ⁿ)	O(n)
Рекурсия + мемоизация	O(n)	O(n)

Как перевести рекурсию в итеративный DP?

Есть простой алгоритм:

1. Понять, что означает f(i)
2. Заменить f(i) на dp[i]
3. Базовые случаи записать в dp
4. Рекурсивный переход записать через цикл
5. Считать dp от маленьких значений к большим

Шаг 1: было рекурсивно

Было:

int fib(int n) {
    if (n == 0) {
        return 0;
    }

    if (n == 1) {
        return 1;
    }

    return fib(n - 1) + fib(n - 2);
}

Здесь состояние:

fib(n) = n-е число Фибоначчи

Шаг 2: заменяем f на dp

Рекурсивная функция:

fib(n)

превращается в массив:

dp[n]

То есть:

fib(0) → dp[0]
fib(1) → dp[1]
fib(i) → dp[i]

Шаг 3: базовые случаи

В рекурсии было:

if (n == 0) return 0;
if (n == 1) return 1;

В итеративном DP это становится:

dp[0] = 0;
dp[1] = 1;

Шаг 4: переход

В рекурсии было:

fib(n) = fib(n - 1) + fib(n - 2)

В массиве будет:

dp[i] = dp[i - 1] + dp[i - 2];

Теперь считаем циклом:

for (int i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
}

Итеративная реализация Фибоначчи

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

long long dp[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    cout << dp[n];

    return 0;
}

Рекурсивный DP vs итеративный DP

Метод	Как работает	Плюс	Минус
Рекурсия + мемоизация	сверху вниз	легко придумать	может быть stack overflow
Итеративный DP	снизу вверх	быстро и стабильно	иногда сложнее понять порядок

Рекурсивный DP часто называют top-down. Итеративный DP часто называют bottom-up.

Пример 2: лестница

Есть лестница из n ступенек. За один ход можно подняться на 1 или на 2 ступеньки. Нужно посчитать количество способов дойти до ступеньки n.

Состояние:

dp[i] = количество способов дойти до ступеньки i

Чтобы попасть на ступеньку i, можно прийти:

со ступеньки i - 1
со ступеньки i - 2

Поэтому:

dp[i] = dp[i - 1] + dp[i - 2];

Лестница: рекурсивный метод

int ways(int n) {
    if (n == 0) {
        return 1;
    }

    if (n == 1) {
        return 1;
    }

    return ways(n - 1) + ways(n - 2);
}

Здесь:

ways(0) = 1
ways(1) = 1
ways(n) = ways(n - 1) + ways(n - 2)

Лестница: рекурсия + мемоизация

const int N = 100010;

long long dp[N];

long long ways(int n) {
    if (n == 0) {
        return 1;
    }

    if (n == 1) {
        return 1;
    }

    if (dp[n] != -1) {
        return dp[n];
    }

    dp[n] = ways(n - 1) + ways(n - 2);
    return dp[n];
}

Лестница: перевод в итеративный метод

Было:

ways(n) = ways(n - 1) + ways(n - 2)

Стало:

dp[i] = dp[i - 1] + dp[i - 2];

Базовые случаи:

dp[0] = 1;
dp[1] = 1;

Лестница: итеративная реализация

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

long long dp[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    dp[0] = 1;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    cout << dp[n];

    return 0;
}

Пример 3: минимальная стоимость

Есть лестница. У каждой ступеньки есть стоимость cost[i]. Можно идти на 1 или 2 ступеньки. Нужно найти минимальную стоимость, чтобы дойти до n.

Состояние:

dp[i] = минимальная стоимость дойти до i

Переход:

dp[i] = cost[i] + min(dp[i - 1], dp[i - 2]);

Минимальная стоимость: рекурсия

int solve(int i) {
    if (i == 1) {
        return cost[1];
    }

    if (i == 2) {
        return cost[2];
    }

    return cost[i] + min(solve(i - 1), solve(i - 2));
}

Это обычная рекурсия. Она может много раз пересчитывать одни и те же значения.

Минимальная стоимость: мемоизация

int solve(int i) {
    if (i == 1) {
        return cost[1];
    }

    if (i == 2) {
        return cost[2];
    }

    if (dp[i] != -1) {
        return dp[i];
    }

    dp[i] = cost[i] + min(solve(i - 1), solve(i - 2));
    return dp[i];
}

Минимальная стоимость: итеративный DP

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n;
int cost[N];
int dp[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> cost[i];
    }

    dp[1] = cost[1];
    dp[2] = cost[2];

    for (int i = 3; i <= n; i++) {
        dp[i] = cost[i] + min(dp[i - 1], dp[i - 2]);
    }

    cout << dp[n];

    return 0;
}

Как думать в DP?

Почти всегда можно идти по такому плану:

1. Что нужно найти?
2. Что будет состоянием dp?
3. Какие базовые случаи?
4. Как перейти к dp[i]?
5. В каком порядке считать?
6. Где лежит ответ?

Главные типы DP

Тип	Пример состояния	Что означает
Количество способов	dp[i]	сколько способов дойти до i
Минимум	dp[i]	минимальная стоимость до i
Максимум	dp[i]	максимальная сумма до i
2D DP	dp[i][j]	ответ для двух параметров

Рекурсия → итерация: короткая схема

Рекурсия	Итеративный DP
f(i)	dp[i]
if (i == 0) return x	dp[0] = x
f(i - 1)	dp[i - 1]
f(i - 2)	dp[i - 2]
return f(i - 1) + f(i - 2)	dp[i] = dp[i - 1] + dp[i - 2]
вызов f(n)	ответ dp[n]

Типичные ошибки

Не понять, что означает dp[i]
Забыть базовые случаи
Считать dp[i], когда dp[i - 1] еще не готов
Перепутать минимум и максимум
Не инициализировать массив dp
В рекурсии забыть мемоизацию
В итерации неправильно выбрать порядок цикла

Асимптотика

Метод	Время	Память
Обычная рекурсия	часто экспоненциально	зависит от глубины
Рекурсия + мемоизация	количество состояний × переход	количество состояний
Итеративный DP	количество состояний × переход	количество состояний

Для простого dp[i] с переходом O(1) сложность обычно O(n).

Короткий шаблон DP

dp[0] = base_value;

for (int i = 1; i <= n; i++) {
    dp[i] = transition_from_previous_states;
}

cout << dp[n];

Короткий шаблон рекурсии с мемоизацией

int solve(int i) {
    if (base_case) {
        return base_value;
    }

    if (dp[i] != -1) {
        return dp[i];
    }

    dp[i] = transition;
    return dp[i];
}

kz-maxx

Введение в динамическое программирование