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

План лекции

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

2. Принцип оптимальности Беллмана

3. Оптимальная подструктура и перекрывающиеся подзадачи

4. Сверху вниз (мемоизация) и снизу вверх (табуляция)

5. Задача о кратчайшем пути

6. Задача о рюкзаке

7. Программная реализация

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

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

Основатель: Ричард Беллман (1957)

Ключевая идея: если решение каждой подзадачи оптимально, то и решение всей задачи оптимально.

Пример

Найти кратчайший маршрут из $A$ в $D$ через промежуточные города:

Вместо перебора всех маршрутов — решаем подзадачи попарно.

2. Принцип оптимальности Беллмана

Принцип оптимальности (Беллман, 1957):

Каково бы ни было начальное состояние и начальное решение, последующие решения должны составлять оптимальное поведение относительно состояния, полученного после первого решения.

Формально: если $\vec{x}^* = (x_1^*, x_2^*, \ldots, x_n^*)$ — оптимальное решение, то для любого $k$ «хвост» $(x_k^*, \ldots, x_n^*)$ оптимален для подзадачи, начинающейся с состояния после $x_{k-1}^*$.

Два ключевых свойства

ДП vs другие подходы

Перекрывающиеся подзадачи: числа Фибоначчи

$$F(n) = F(n-1) + F(n-2), \quad F(0) = 0, \quad F(1) = 1$$

Дерево рекурсии для $F(5)$:

Дублирующиеся вычисления: $F(3)$ вычисляется 2 раза, $F(2)$ — 3 раза.

Наивная рекурсия: $O(2^n)$. С мемоизацией: $O(n)$.

3. Подходы к реализации ДП

Пример: числа Фибоначчи — мемоизация

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(50))  # 12586269025

Характеристики:

• Время: $O(n)$ — каждая подзадача решается один раз
• Память: $O(n)$ — кэш + стек вызовов $O(n)$

Пример: числа Фибоначчи — табуляция

def fib_tab(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

print(fib_tab(50))  # 12586269025

Характеристики:

• Время: $O(n)$
• Память: $O(n)$ — можно сократить до $O(1)$, храня только два последних значения

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

def fib_opt(n):
    if n <= 1:
        return n
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

print(fib_opt(50))  # 12586269025

Характеристики:

• Время: $O(n)$
• Память: $O(1)$ — только две переменные

Приём: анализируйте, какие предыдущие состояния нужны для текущего шага, и храните только их.

4. Задача о кратчайшем пути

Постановка: найти путь минимальной стоимости от вершины $s$ до вершины $t$ во взвешенном графе.

Варианты:

• От одного источника ко всем вершинам
• Между всеми парами вершин

Алгоритм Беллмана-Форда

Идея: последовательно улучшать оценки кратчайших расстояний, проходя по всем рёбрам.

Рекуррентное соотношение (Беллмана):

$$d^{(k)}[v] = \min \left( d^{(k-1)}[v],\; \min_{(u,v) \in E} \left\{ d^{(k-1)}[u] + w(u,v) \right\} \right)$$

$d^{(k)}[v]$ — кратчайшее расстояние от $s$ до $v$, использующее не более $k$ рёбер.

Базовый случай: $d^{(0)}[s] = 0$, $d^{(0)}[v] = \infty$ для $v \neq s$.

Алгоритм Беллмана-Форда: шаги

Вход: граф $G = (V, E)$, веса $w$, источник $s$

1. Инициализация: $d[s] = 0$, $d[v] = \infty$ для $v \neq s$
2. Повторить $|V| - 1$ раз:
   • Для каждого ребра $(u, v) \in E$:
   • Если $d[u] + w(u,v) < d[v]$: $d[v] = d[u] + w(u,v)$
3. Проверка отрицательных циклов:
   • Для каждого ребра $(u, v) \in E$:
   • Если $d[u] + w(u,v) < d[v]$ → отрицательный цикл

Сложность: $O(|V| \cdot |E|)$

Пример: алгоритм Беллмана-Форда

Пример: результаты

Кратчайшие расстояния от $A$:

Итерация 4: никаких изменений — ранняя остановка.

Алгоритм Флойда-Уоршелла

Идея: кратчайший путь через промежуточные вершины из множества $\{1, 2, \ldots, k\}$.

Рекуррентное соотношение:

$$d_{ij}^{(k)} = \min \left( d_{ij}^{(k-1)},\; d_{ik}^{(k-1)} + d_{kj}^{(k-1)} \right)$$

• $d_{ij}^{(0)} = w(i,j)$ — вес ребра (или $\infty$, если ребра нет)
• $d_{ij}^{(k)}$ — кратчайший путь от $i$ до $j$ через вершины $\{1, \ldots, k\}$
• $d_{ij}^{(n)}$ — кратчайший путь вообще

Сложность: $O(|V|^3)$, память: $O(|V|^2)$

Пример: алгоритм Флойда-Уоршелла

   A  B  C
A  0  3  ∞
B  2  0  1
C  ∞  5  0

5. Задача о рюкзаке

Постановка: есть $n$ предметов с весом $w_i$ и стоимостью $c_i$. Рюкзак вмещает вес не более $W$. Какие предметы положить, чтобы суммарная стоимость была максимальной?

$$\max \sum_{i=1}^{n} c_i x_i \quad \text{при} \quad \sum_{i=1}^{n} w_i x_i \leq W, \quad x_i \in \{0, 1\}$$

Варианты:

• 0/1 рюкзак — каждый предмет берётся целиком или не берётся
• Неограниченный рюкзак — предмет можно брать многократно

Рекуррентное соотношение для задачи о рюкзаке

Пусть $dp[i][w]$ — максимальная стоимость, используя первые $i$ предметов при вместимости $w$.

$$dp[i][w] = \begin{cases} dp[i-1][w] & \text{если } w_i > w \text{ (не помещается)} \\ \max(dp[i-1][w],\; dp[i-1][w - w_i] + c_i) & \text{иначе} \end{cases}$$

Базовый случай: $dp[0][w] = 0$ для всех $w$.

Ответ: $dp[n][W]$

Сложность: $O(n \cdot W)$ — псевдополиномиальная

Пример: задача о рюкзаке

Вместимость рюкзака: $W = 8$

Пример: заполнение таблицы

$dp[i][w]$ — максимальная стоимость:

Ответ: $dp[4][8] = 12$

Пример: восстановление решения

Обратный проход от $dp[4][8] = 12$:

Оптимальный набор: предметы 1 и 2, вес $2 + 3 = 5 \leq 8$, стоимость $3 + 4 = 7$.

Исправление: повторим — предмет 4 при $w = 8$: $dp[3][3] + 8 = 4 + 8 = 12 = dp[4][8]$ ✓

Оптимальный набор: предметы 2 и 4, вес $3 + 5 = 8$, стоимость $4 + 8 = 12$.

6. Программная реализация: задача о рюкзаке

def knapsack(weights, costs, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(W + 1):
            dp[i][w] = dp[i - 1][w]
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i][w],
                    dp[i - 1][w - weights[i - 1]] + costs[i - 1])

    # Восстановление решения
    w, result = W, []
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i - 1][w]:
            result.append(i - 1)
            w -= weights[i - 1]

    return dp[n][W], result

val, items = knapsack([2, 3, 4, 5], [3, 4, 5, 8], 8)
print(f"Стоимость: {val}, Предметы: {items}")
# Стоимость: 12, Предметы: [3, 1]

Программная реализация: Беллман-Форд

def bellman_ford(n, edges, s):
    d = [float('inf')] * n
    d[s] = 0
    p = [-1] * n

    for _ in range(n - 1):
        for u, v, w in edges:
            if d[u] + w < d[v]:
                d[v] = d[u] + w
                p[v] = u

    # Проверка отрицательных циклов
    for u, v, w in edges:
        if d[u] + w < d[v]:
            raise ValueError("Отрицательный цикл")

    # Восстановление пути
    def path(t):
        route = []
        while t != -1:
            route.append(t)
            t = p[t]
        return route[::-1]

    return d, path

Программная реализация: Флойда-Уоршелл

def floyd_warshall(n, dist):
    d = [row[:] for row in dist]
    p = [[i if dist[i][j] < float('inf') else -1
          for j in range(n)] for i in range(n)]

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]
                    p[i][j] = p[k][j]

    return d, p

Заключение

Ключевые выводы лекции

Вопросы для самоконтроля

1. Сформулируйте принцип оптимальности Беллмана.
2. Какие два свойства необходимы для применения ДП?
3. В чём разница между мемоизацией и табуляцией?
4. Запишите рекуррентное соотношение алгоритма Беллмана-Форда.
5. Какова сложность алгоритма Флойда-Уоршелла?
6. Запишите рекуррентное соотношение задачи о рюкзаке (0/1).
7. Как восстановить решение по таблице ДП?
8. Почему задача о рюкзаке имеет псевдополиномиальную сложность?

Рекомендуемые ресурсы