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

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

Когда применять DP?

DP применимо, когда задача обладает двумя свойствами:

1. Оптимальная подструктура — оптимальное решение задачи содержит оптимальные решения подзадач
2. Перекрывающиеся подзадачи — одни и те же подзадачи решаются многократно

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

Рассмотрим классическую задачу: вычислить n-е число Фибоначчи.

Наивная рекурсия (плохо)

def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

# fib_naive(40) выполняется очень долго!

Проблема: Временная сложность O(2^n) — экспоненциальная!

Посмотрим на дерево вызовов для fib(5):

                    fib(5)
                   /      \
              fib(4)      fib(3)
             /    \       /    \
         fib(3)  fib(2) fib(2) fib(1)
         /   \    /  \   /  \
      fib(2) fib(1) ...  ...

Видите? fib(3) вычисляется 2 раза, fib(2) — 3 раза. Это и есть перекрывающиеся подзадачи.

Подход 1: Мемоизация (Top-Down)

Мемоизация — это сохранение результатов уже решённых подзадач.

def fib_memo(n, memo=None):
    if memo is None:
        memo = {}

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

# Если уже вычисляли — возвращаем из кэша
if n in memo:
    return memo[n]

# Базовые случаи
if n <= 1:
    return n

# Вычисляем и сохраняем
memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
return memo[n]

Теперь fib_memo(40) работает мгновенно!

**JavaScript версия:**

```javascript
function fibMemo(n, memo = {}) {
    if (n in memo) return memo[n];
    if (n <= 1) return n;

    memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    return memo[n];
}

Временная сложность: O(n) Пространственная сложность: O(n)

Подход 2: Табуляция (Bottom-Up)

Табуляция — это заполнение таблицы решений снизу вверх.

def fib_tab(n):
    if n <= 1:
        return n

    # Создаём таблицу
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1

    # Заполняем снизу вверх
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

Оптимизация по памяти:

def fib_optimized(n):
    if n <= 1:
        return n

    prev2, prev1 = 0, 1

    for i in range(2, n + 1):
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current

    return prev1

# Пространственная сложность: O(1)!

Мемоизация vs Табуляция

Классическая задача 1: Climbing Stairs

Условие: Вы поднимаетесь по лестнице из n ступенек. За раз можно подняться на 1 или 2 ступеньки. Сколько существует способов добраться до вершины?

Анализ задачи

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

• Ступеньки n-1 (шаг на 1)
• Ступеньки n-2 (шаг на 2)

Формула: dp[n] = dp[n-1] + dp[n-2]

Это же числа Фибоначчи!

def climb_stairs(n):
    if n <= 2:
        return n

    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2

    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

# Примеры:
# climb_stairs(2) = 2  (1+1 или 2)
# climb_stairs(3) = 3  (1+1+1, 1+2, 2+1)
# climb_stairs(4) = 5  (1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2)

Классическая задача 2: Coin Change

Условие: Дан набор монет разного номинала и сумма. Найти минимальное количество монет для набора этой суммы.

Пример

Монеты: [1, 2, 5]
Сумма: 11

Ответ: 3 (5 + 5 + 1)

Решение

def coin_change(coins, amount):
    # dp[i] = минимум монет для суммы i
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # Для суммы 0 нужно 0 монет

    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] != float('inf'):
                dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

# coin_change([1, 2, 5], 11) = 3

Визуализация для amount = 6, coins = [1, 3, 4]

Сумма:    0   1   2   3   4   5   6
Монет:    0   1   2   1   1   2   2

Объяснение:
- dp[0] = 0 (база)
- dp[1] = dp[0] + 1 = 1 (монета 1)
- dp[2] = dp[1] + 1 = 2 (1+1)
- dp[3] = dp[0] + 1 = 1 (монета 3)
- dp[4] = dp[0] + 1 = 1 (монета 4)
- dp[5] = dp[4] + 1 = 2 (4+1)
- dp[6] = dp[3] + 1 = 2 (3+3)

Классическая задача 3: 0/1 Knapsack (Рюкзак)

Условие: Есть рюкзак вместимостью W и n предметов с весом и ценностью. Выбрать предметы так, чтобы максимизировать ценность, не превысив вместимость.

Пример

Вместимость: 7
Предметы:
  Вес: [1, 3, 4, 5]
  Ценность: [1, 4, 5, 7]

Ответ: 9 (предметы с весом 3 и 4, ценность 4+5)

Решение

def knapsack(weights, values, capacity):
    n = len(weights)
    # dp[i][w] = макс. ценность для первых i предметов и вместимости w
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            # Не берём предмет i
            dp[i][w] = dp[i - 1][w]

            # Берём предмет i (если влезает)
            if weights[i - 1] <= w:
                dp[i][w] = max(
                    dp[i][w],
                    dp[i - 1][w - weights[i - 1]] + values[i - 1]
                )

    return dp[n][capacity]

# knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7) = 9

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

def knapsack_optimized(weights, values, capacity):
    dp = [0] * (capacity + 1)

    for i in range(len(weights)):
        # Важно: идём справа налево!
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

    return dp[capacity]

Паттерны динамического программирования

Паттерн 1: Линейное DP

Состояние зависит от предыдущих элементов в одномерном массиве.

Примеры задач:

• Fibonacci
• Climbing Stairs
• House Robber
• Maximum Subarray

# Шаблон
dp = [0] * n
dp[0] = base_case

for i in range(1, n):
    dp[i] = f(dp[i-1], dp[i-2], ...)  # рекуррентное соотношение

Паттерн 2: Двумерное DP

Состояние зависит от двух параметров.

Примеры задач:

• Unique Paths
• Minimum Path Sum
• Longest Common Subsequence
• Edit Distance

# Шаблон
dp = [[0] * m for _ in range(n)]

for i in range(n):
    for j in range(m):
        dp[i][j] = f(dp[i-1][j], dp[i][j-1], ...)

Паттерн 3: Интервальное DP

Решение для интервала [i, j] зависит от меньших интервалов.

Примеры задач:

• Longest Palindromic Subsequence
• Matrix Chain Multiplication
• Burst Balloons

# Шаблон
for length in range(2, n + 1):  # длина интервала
    for i in range(n - length + 1):  # начало интервала
        j = i + length - 1  # конец интервала
        for k in range(i, j):  # точка разбиения
            dp[i][j] = f(dp[i][k], dp[k+1][j])

Паттерн 4: DP на подмножествах (Bitmask DP)

Используется для задач на перебор подмножеств.

Примеры задач:

• Travelling Salesman Problem
• Partition Equal Subset Sum

# Шаблон
dp = [inf] * (1 << n)  # 2^n состояний
dp[0] = 0

for mask in range(1 << n):
    for i in range(n):
        if mask & (1 << i):  # i-й элемент в подмножестве
            dp[mask] = f(dp[mask ^ (1 << i)], ...)

Как решать DP задачи: пошаговый алгоритм

Шаг 1: Определите состояние

Спросите себя: "Что нужно знать, чтобы принять решение?"

Пример (Coin Change):

• Нужно знать: оставшуюся сумму
• Состояние: dp[amount] = минимум монет

Шаг 2: Найдите рекуррентное соотношение

Как текущее состояние связано с предыдущими?

Пример (Coin Change):

dp[amount] = min(dp[amount - coin] + 1) для всех монет

Шаг 3: Определите базовые случаи

Какие состояния известны изначально?

Пример (Coin Change):

dp[0] = 0  (для суммы 0 нужно 0 монет)

Шаг 4: Определите порядок вычисления

В каком порядке заполнять таблицу?

Пример (Coin Change):

От 1 до amount (слева направо)

Шаг 5: Оптимизируйте (если нужно)

Можно ли уменьшить пространственную сложность?

Практика: решаем Longest Increasing Subsequence

Условие: Найти длину самой длинной возрастающей подпоследовательности.

Вход: [10, 9, 2, 5, 3, 7, 101, 18]
Выход: 4
Объяснение: [2, 3, 7, 101] или [2, 3, 7, 18]

Решение O(n^2)

def longest_increasing_subsequence(nums):
    if not nums:
        return 0

    n = len(nums)
    # dp[i] = длина LIS, заканчивающейся на nums[i]
    dp = [1] * n

    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

Визуализация

nums: [10,  9,  2,  5,  3,  7, 101, 18]
dp:   [ 1,  1,  1,  2,  2,  3,   4,  4]

Объяснение:
- dp[0] = 1 (только 10)
- dp[1] = 1 (только 9, нет меньших слева)
- dp[2] = 1 (только 2)
- dp[3] = 2 (2 < 5, поэтому 2→5)
- dp[4] = 2 (2 < 3, поэтому 2→3)
- dp[5] = 3 (2→3→7 или 2→5→7)
- dp[6] = 4 (2→3→7→101)
- dp[7] = 4 (2→3→7→18)

Типичные ошибки и как их избежать

Ошибка 1: Неправильные базовые случаи

# Плохо
dp = [0] * n  # Иногда 0 — неправильное начальное значение

# Хорошо: подумайте, что означает dp[0]
dp = [float('inf')] * n  # Для задач на минимум
dp[0] = 0  # Явный базовый случай

Ошибка 2: Неправильный порядок обхода

# Для 0/1 Knapsack с оптимизацией памяти
# Плохо: слева направо (один предмет берётся много раз)
for w in range(weight, capacity + 1):
    ...

# Хорошо: справа налево
for w in range(capacity, weight - 1, -1):
    ...

Ошибка 3: Забыли про edge cases

def solve(arr):
    if not arr:  # Пустой массив
        return 0
    if len(arr) == 1:  # Один элемент
        return arr[0]

    # Основная логика

Задачи для практики (по сложности)

Easy

1. Climbing Stairs — базовое линейное DP
2. House Robber — выбор с ограничениями
3. Maximum Subarray — алгоритм Кадане
4. Best Time to Buy and Sell Stock — отслеживание минимума

Medium

1. Coin Change — классика unbounded knapsack
2. Longest Increasing Subsequence — O(n^2) или O(n log n)
3. Unique Paths — 2D grid DP
4. Word Break — строковое DP
5. Decode Ways — подсчёт вариантов

Hard

1. Edit Distance — 2D DP на строках
2. Longest Valid Parentheses — сложное состояние
3. Regular Expression Matching — многомерное DP
4. Burst Balloons — интервальное DP

Заключение

Динамическое программирование — это навык, который развивается с практикой. Ключевые выводы:

1. Ищите перекрывающиеся подзадачи — если решаете одно и то же несколько раз, нужно DP
2. Начинайте с рекурсии — сначала напишите рекурсивное решение, потом добавьте мемоизацию
3. Практикуйте паттерны — большинство задач укладываются в известные шаблоны
4. Рисуйте таблицы — визуализация помогает понять логику заполнения

Рекомендуемый порядок изучения:

1. Числа Фибоначчи → понимание мемоизации
2. Climbing Stairs → линейное DP
3. Coin Change → unbounded knapsack
4. 0/1 Knapsack → bounded knapsack
5. LIS, LCS → классические задачи
6. Grid DP → двумерные задачи
7. Interval DP → продвинутые техники

Удачи в изучении DP!