W5–W6. Динамическое программирование (DP), максимальный подмассив, НОП (LCS), rod cutting, рюкзак 0–1

Автор

Nikolai Kudasov

Дата публикации

16 февраля 2026 г.

1. Краткое содержание

1.1 Введение в динамическое программирование (DP)

Динамическое программирование (dynamic programming, DP) — мощный алгоритмический приём для задач оптимизации (optimization problems): задача разбивается на перекрывающиеся подзадачи (overlapping subproblems), каждая подзадача решается один раз, а результаты запоминаются, чтобы не повторять лишние вычисления. В отличие от divide and conquer, где подзадачи независимы, DP опирается на то, что одна и та же подзадача может встречаться в разных ветках рекурсии многократно.

Название «динамическое программирование» слегка обманчиво: оно не про «динамическое написание программ». Термин ввёл Ричард Беллман в 1950-х. Здесь programming — в смысле оптимизации (как в linear programming), а dynamic — про поэтапное решение во времени.

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

DP уместен, если у задачи есть два ключевых свойства:

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

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

1.1.2 Задачи оптимизации

Задача оптимизации (optimization problem) имеет такую структуру:

  1. Может быть много допустимых решений (кандидатов).
  2. У каждого решения есть значение (value) (обычно число).
  3. Нужно найти решение с оптимальным значением (минимум или максимум).

Оптимальных решений с тем же оптимальным значением может быть несколько. DP помогает найти хотя бы одно эффективно.

Примеры задач оптимизации, которые уже встречались:

  • Сортировка: среди всех перестановок массива найти ту, что даёт отсортированный порядок.
  • Кратчайший путь: среди всех путей между двумя вершинами — путь с минимальной суммой длин рёбер.
  • Максимальный подмассив (maximum subarray): среди всех подотрезков — подотрезок с максимальной суммой.
1.2 Шаги построения DP-алгоритма

Есть четыре опорных шага:

Шаг 1: Описать структуру оптимального решения

Разобраться, как оптимум исходной задачи собирается из оптимумов подзадач. Здесь важно увидеть рекурсивную структуру.

Важно: чтобы DP было выгодно, оптимальное решение должно переиспользовать ответы на перекрывающиеся подзадачи. Если подзадачи не пересекаются по работе (как в merge sort), чаще уместен divide and conquer, а не DP.

Шаг 2: Рекурсивно определить значение оптимального решения

Выразить значение оптимума через значения на меньших подзадачах — обычно это рекуррентное соотношение (recurrence relation).

Шаг 3: Вычислить значения оптимальных решений

Использовать bottom-up (табуляция, tabulation) или top-down (мемоизация, memoization) так, чтобы каждая подзадача решалась один раз.

Шаг 4: Восстановить само оптимальное решение

По данным, накопленным при вычислении значений, построить конкретный оптимальный объект (не только число).

Замечание: шаг 4 не нужен, если требуется только оптимальное значение.

1.3 Bottom-up и top-down

Два основных способа реализации DP:

1.3.1 Bottom-up (табуляция, tabulation)

Итеративно строим ответы от меньших подзадач к большим:

  1. Инициализировать таблицу (массив) для хранения решений подзадач.
  2. Заполнить таблицу, начиная с самых маленьких подзадач.
  3. Считать ответ к исходной задаче из таблицы.

Плюсы:

  • Обычно быстрее на практике (нет накладных расходов на рекурсивные вызовы).
  • Проще анализировать space complexity.
  • Часто можно сжать память, выкидывая уже ненужные слои таблицы.

Минусы:

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

Пример: числа Фибоначчи от \(F_0\), \(F_1\) вверх до \(F_n\).

1.3.2 Top-down (мемоизация, memoization)

Рекурсия + кэш:

  1. Рекурсивная функция сначала проверяет, есть ли результат для данных параметров.
  2. Если да — возвращает значение из кэша.
  3. Иначе считает рекурсивно и сохраняет в кэш перед возвратом.

Плюсы:

  • Ближе к «естественной» рекурсивной формулировке.
  • Считаются только нужные подзадачи.
  • Часто легко получить из наивной рекурсии, просто добавив кэш.

Минусы:

  • Накладные расходы на вызовы.
  • Риск stack overflow при большой глубине.
  • Сложнее ужимать память.

Пример: Фибоначчи со словарём/картой для уже вычисленных значений.

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

Последовательность Фибоначчи — классическая иллюстрация разрыва между наивной рекурсией и DP.

Последовательность: \(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, \ldots\)

Рекуррентность: \(F_n = F_{n-1} + F_{n-2}\) при \(F_0 = 0\) и \(F_1 = 1\).

1.4.1 Наивная рекурсия
def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

Анализ:

  • Временная сложность: \(\Theta(\phi^n)\), где \(\phi = \frac{1+\sqrt{5}}{2} \approx 1.618\) (golden ratio)
    • Из \(T(n) = T(n-1) + T(n-2) + O(1)\) получаем экспоненциальный рост
    • Верхняя оценка: \(T(n) \le 2T(n-1) = O(2^n)\)
    • Более точно: \(T(n) = \Theta(F_n) = \Theta(\phi^n)\)
  • Память: \(\Theta(n)\) из‑за глубины стека

Почему медленно? В дереве вызовов огромная избыточность: например, для f(6) значение f(4) считается дважды, f(3) — трижды, f(2) — пять раз и т.д.; число вызовов растёт экспоненциально.

1.4.2 Bottom-up DP
def fibonacci(n):
    fib = [0] * (n + 1)
    fib[0] = 0
    fib[1] = 1
    for i in range(2, n + 1):
        fib[i] = fib[i - 1] + fib[i - 2]
    return fib[n]

Анализ:

  • Время: \(\Theta(n)\) — один проход от \(2\) до \(n\)
  • Память: \(\Theta(n)\) на массив

Можно ли по памяти? Да: нужны только два предыдущих значения — две переменные, \(\Theta(1)\) дополнительной памяти:

def fibonacci(n):
    if n == 0: return 0
    if n == 1: return 1
    prev2, prev1 = 0, 1
    for i in range(2, n + 1):
        current = prev1 + prev2
        prev2, prev1 = prev1, current
    return prev1
1.4.3 Top-down DP (мемоизация)
def fibonacci(n):
    memo = {}
    return fib_memo(n, memo)

def fib_memo(n, memo):
    if n in memo:
        return memo[n]
    if n == 0:
        result = 0
    elif n == 1:
        result = 1
    else:
        result = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    memo[n] = result
    return result

Анализ:

  • Время: \(\Theta(n)\) — каждое \(n\) вычисляется ровно один раз
  • Память: \(\Theta(n)\) на словарь и стек рекурсии
1.5 Задача о максимальном подмассиве (maximum subarray)
1.5.1 Постановка

Вход: последовательность из \(n\) чисел \(\langle a_1, a_2, \ldots, a_n \rangle\).

Выход: индексы \(l\) и \(r\) такие, что \(\sum_{i=l}^{r} a_i\) максимально среди всех \(1 \le l \le r \le n\).

Применения:

  1. Анализ временных рядов: интервалы максимального прироста или просадки
  2. Трейдинг: лучший период удержания, если по дням заданы приращения цены
  3. Обработка сигналов: участки максимальной «энергии»

Пример: для \(A = [-2, 1, -3, 4, -1, 2, 1, -5, 4]\) максимальный подотрезок — \([4, -1, 2, 1]\) (индексы 4–7), сумма \(6\).

Что уже было:

  • Полный перебор: все \(O(n^2)\) подотрезков — время \(\Theta(n^2)\)
  • Divide and conquer: лево, право, пересекающийся случай — \(\Theta(n \log n)\)

Дальше — DP-решение за \(\Theta(n)\).

1.5.2 Идея DP

Для каждой позиции \(i\) введём:

  • maxSuffixValue(A, i): максимальная сумма подотрезка, заканчивающегося в \(i\)
  • maxSuffix(A, i): индекс начала такого суффикса с максимальной суммой

Ключевое наблюдение: лучший суффикс, заканчивающийся в \(i\), либо

  1. продолжает лучший суффикс для \(i-1\) (если его сумма положительна), либо
  2. начинается заново в \(i\) (если продолжение ухудшает сумму)

Рекуррентность для суммы суффикса:

\[\text{maxSuffixValue}(A, i) = \begin{cases} A[1], & \text{if } i = 1 \\ \max(\text{maxSuffixValue}(A, i-1) + A[i], A[i]), & \text{otherwise} \end{cases}\]

Почему так: если лучший суффикс для \(i-1\) даёт положительный вклад, разумно добавить \(A[i]\); если нет — выгоднее взять только \(A[i]\).

Рекуррентность для начала суффикса:

\[\text{maxSuffix}(A, i) = \begin{cases} 1, & \text{if } i = 1 \\ j, & \text{if } j = \text{maxSuffix}(A, i-1) \text{ and } \text{maxSuffixValue}(A, i-1) > 0 \\ i, & \text{otherwise} \end{cases}\]

Глобальный максимум:

\[\text{maxSum} = \max_{1 \le i \le n} \text{maxSuffixValue}(A, i)\]

1.5.3 Алгоритм Кадане (Kadane’s algorithm)

Bottom-up реализация этой идеи — алгоритм Кадане (Kadane’s algorithm):

def max_subarray(A, n):
    max_suffix_sum = A[1]
    max_sum = max_suffix_sum
    for i in range(2, n + 1):
        max_suffix_sum = max(max_suffix_sum + A[i], A[i])
        max_sum = max(max_sum, max_suffix_sum)
    return max_sum

Как читать код:

  • max_suffix_sum — максимальная сумма подотрезка, заканчивающегося в текущей позиции
  • max_sum — лучшая сумма среди всех префиксов «до текущего \(i\)»
  • на каждом шаге выбор: продлить текущий отрезок или начать новый

Анализ:

  • Время: \(\Theta(n)\) — один проход
  • Память: \(\Theta(1)\)

Это оптально по порядку: без просмотра каждого элемента задачу не решить.

Индексы подотрезка: дополнительно хранятся границы текущего суффикса и лучшего ответа:

def max_subarray_with_indices(A, n):
    max_suffix_sum = A[1]
    max_sum = max_suffix_sum
    start = 1  # start of current suffix
    best_start = 1  # start of best subarray
    best_end = 1    # end of best subarray

    for i in range(2, n + 1):
        if max_suffix_sum + A[i] > A[i]:
            max_suffix_sum = max_suffix_sum + A[i]
        else:
            max_suffix_sum = A[i]
            start = i  # start new suffix here

        if max_suffix_sum > max_sum:
            max_sum = max_suffix_sum
            best_start = start
            best_end = i

    return (best_start, best_end, max_sum)
1.6 Наибольшая общая подпоследовательность (LCS)
1.6.1 Подпоследовательности

Последовательность \(Z = \langle z_1, z_2, \ldots, z_k \rangle\) — подпоследовательность (subsequence) \(X = \langle x_1, x_2, \ldots, x_m \rangle\), если существует строго возрастающая последовательность индексов \(\langle i_1, i_2, \ldots, i_k \rangle\) такая, что \(z_j = x_{i_j}\) для всех \(j\).

Проще: \(Z\) получается из \(X\) удалением некоторых элементов (возможно, нуля) без перестановки оставшихся.

Примеры:

  • \(\langle B, D, A \rangle\) — подпоследовательность \(\langle A, B, C, B, D, A, B \rangle\) (индексы 2, 5, 6)
  • \(\langle B, C, D, B \rangle\) — тоже подпоследовательность (2, 3, 5, 7)
  • \(\langle A, C, D, C \rangle\) — не подпоследовательность: после \(C\) в позиции 3 и \(D\) в позиции 5 второго \(C\) справа уже нет

Отличие от подстроки (substring): подстрока непрерывна, подпоследовательность — нет.

1.6.2 Общие подпоследовательности

\(Z\) — общая подпоследовательность (common subsequence) \(X\) и \(Y\), если \(Z\) — подпоследовательность и \(X\), и \(Y\).

Пример: \(X = \langle A, B, C, B, D, A, B \rangle\), \(Y = \langle B, D, C, A, B, A \rangle\):

  • \(\langle B, C, A \rangle\) — общая подпоследовательность
  • \(\langle B, C, D \rangle\) — не общая (не укладывается в \(Y\) по порядку)
  • \(\langle B, C, A, B \rangle\) — общая
1.6.3 Постановка LCS

Задача LCS (longest common subsequence):

Вход: две последовательности \(X = \langle x_1, x_2, \ldots, x_m \rangle\) и \(Y = \langle y_1, y_2, \ldots, y_n \rangle\).

Выход: общая подпоследовательность максимальной длины.

Применения:

  1. Сходство текстов и строк
  2. Биоинформатика: сравнение цепочек
  3. Контроль версий: diff между файлами
  4. Поиск заимствований

Наивно:

  1. Перебрать все \(2^m\) подпоследовательностей \(X\)
  2. Для каждой проверить вхождение в \(Y\) за \(O(n)\)
  3. Запомнить самую длинную

Время: \(O(n \cdot 2^m)\) — на практике неприемлемо уже при умеренных \(m\).

1.6.4 Оптимальная подструктура

Теорема (оптимальная подструктура LCS):

Пусть \(X_i = \langle x_1, \ldots, x_i \rangle\) — префикс \(X\) длины \(i\), аналогично \(Y_j\). Пусть \(Z_k = \langle z_1, \ldots, z_k \rangle\) — НОП для \(X\) и \(Y\). Тогда:

  1. Если \(x_m = y_n\): тогда \(z_k = x_m = y_n\) и \(Z_{k-1}\) — НОП для \(X_{m-1}\) и \(Y_{n-1}\).

    Смысл: совпавший «хвост» обязан участвовать в НОП; убираем его и решаем меньшую задачу.

  2. Если \(x_m \neq y_n\): тогда либо

    • \(z_k \neq x_m\), и тогда \(Z_k\) — НОП для \(X_{m-1}\) и \(Y_n\), либо
    • \(z_k \neq y_n\), и тогда \(Z_k\) — НОП для \(X_m\) и \(Y_{n-1}\)

    Смысл: хотя бы один из последних символов не входит в НОП; пробуем оба варианта и берём лучший.

Отсюда — естественная схема для DP.

1.6.5 Рекурсивная формула для длины

Пусть \(\text{LCS}'(X_m, Y_n)\) — длина НОП для префиксов \(X_m\) и \(Y_n\):

\[\text{LCS}'(X_m, Y_n) = \begin{cases} 0, & \text{if } m = 0 \text{ or } n = 0 \\ 1 + \text{LCS}'(X_{m-1}, Y_{n-1}), & \text{if } x_m = y_n \\ \max(\text{LCS}'(X_{m-1}, Y_n), \text{LCS}'(X_m, Y_{n-1})), & \text{otherwise} \end{cases}\]

База: пустые строки дают длину 0.

Шаги:

  • Совпали символы: прибавляем 1 и решаем задачу на префиксах без последних символов
  • Не совпали: пробуем отбросить символ в \(X\) или в \(Y\) и берём максимум
1.6.6 Bottom-up: таблицы \(C\) и \(B\)

Строим таблицу \(C[i, j]\) — длина НОП для \(X_i\) и \(Y_j\).

Таблица \(B[i, j]\) фиксирует, откуда пришёл переход (для восстановления ответа):

  • “XY” (стрелка «↖»): совпадение, переход из \(C[i-1, j-1]\)
  • “X” («←»): из \(C[i, j-1]\) (исключили \(y_j\))
  • “Y” («↑»): из \(C[i-1, j]\) (исключили \(x_i\))

Алгоритм:

def LCS_length(X, m, Y, n):
    # Create tables
    B = [[None] * n for _ in range(m)]  # 1-indexed
    C = [[0] * (n + 1) for _ in range(m + 1)]  # 0-indexed

    # Initialize base cases
    for i in range(1, m + 1):
        C[i][0] = 0
    for j in range(1, n + 1):
        C[0][j] = 0

    # Fill the table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i] == Y[j]:
                C[i][j] = C[i - 1][j - 1] + 1
                B[i][j] = "XY"  # diagonal arrow
            elif C[i][j - 1] < C[i - 1][j]:
                C[i][j] = C[i - 1][j]
                B[i][j] = "Y"   # up arrow
            else:
                C[i][j] = C[i][j - 1]
                B[i][j] = "X"   # left arrow

    return C, B

Анализ:

  • Время: \(\Theta(m \cdot n)\)
  • Память: \(\Theta(m \cdot n)\)

Восстановление НОП: идти от \(B[m, n]\) по стрелкам назад:

def reconstruct_LCS(B, X, i, j):
    if i == 0 or j == 0:
        return []
    if B[i][j] == "XY":
        return reconstruct_LCS(B, X, i-1, j-1) + [X[i]]
    elif B[i][j] == "Y":
        return reconstruct_LCS(B, X, i-1, j)
    else:
        return reconstruct_LCS(B, X, i, j-1)
1.7 Классические задачи DP
1.7.1 Rod cutting (резание стержня)

Задача: есть стержень длины \(n\); его режут на куски; для каждой длины \(i\) известна цена \(p[i]\); разрезы бесплатны. Как резать, чтобы максимизировать выручку?

Вход: \(n\) и таблица цен \(p[1 \ldots n]\).

Выход: способ разрезания с максимальной суммарной ценой кусков.

Пример: \(n = 7\) и цены:

Длина (м) 1 2 3 4 5 6 7
Цена ($) 1 5 8 9 10 17 17

Варианты:

  • Не резать: выручка \(17\)
  • \(1 + 6\): \(1 + 17 = 18\) ✓ (оптимум)
  • \(2 + 2 + 3\): \(5 + 5 + 8 = 18\) ✓ (тоже оптимум)

Оптимальная подструктура: максимальная выручка \(r_n\) для длины \(n\):

  1. отрезаем кусок длины \(i\) (\(1 \le i \le n\)), получаем \(p_i\),
  2. остаток длины \(n-i\) режем оптимально.

Рекуррентность:

\[r_n = \max_{1 \le i \le n} (p_i + r_{n-i})\]

с базой \(r_0 = 0\).

Bottom-up:

def rod_cutting(p, n):
    r = [0] * (n + 1)
    for j in range(1, n + 1):
        max_revenue = -float('inf')
        for i in range(1, j + 1):
            max_revenue = max(max_revenue, p[i] + r[j - i])
        r[j] = max_revenue
    return r[n]

Время: \(\Theta(n^2)\); память: \(\Theta(n)\).

1.7.2 Рюкзак 0–1 (0–1 knapsack)

Задача: рюкзак грузоподъёмностью \(W\) и \(n\) предметов с весами \(w_i\) и ценностями \(v_i\). Выбрать подмножество с максимальной суммарной ценностью при ограничении \(\sum w_i \le W\); каждый предмет берётся не более одного раза.

Вход: \(W\), массивы \(w[1 \ldots n]\) и \(v[1 \ldots n]\).

Выход: подмножество \(S \subseteq \{1, \ldots, n\}\) с максимумом \(\sum_{i \in S} v_i\) при \(\sum_{i \in S} w_i \le W\).

Пример: \(W = 35\) кг:

Предмет Suitcase Tablet Laptop Water Tent Plug Bed
Вес (кг) 12 2 6 3 24 1 9
Ценность ($) 36 4 24 2 64 1 22

Почему жадный по отношению ценность/вес не всегда верен: локально «выгодный» предмет может вытеснить комбинацию с лучшим суммарным эффектом.

Оптимальная подструктура: \(K(i, w)\) — максимальная ценность по первым \(i\) предметам при лимите веса \(w\):

\[K(i, w) = \begin{cases} 0, & \text{if } i = 0 \text{ or } w = 0 \\ K(i-1, w), & \text{if } w_i > w \text{ (item too heavy)} \\ \max(K(i-1, w), v_i + K(i-1, w - w_i)), & \text{otherwise} \end{cases}\]

Смысл:

  • База: нет предметов или нет вместимости — ценность 0
  • Не помещается: вариант с предметом \(i\) недоступен
  • Помещается: сравниваем «не брать \(i\)» и «взять \(i\)»

DP:

def knapsack(W, w, v, n):
    K = [[0] * (W + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for wt in range(1, W + 1):
            if w[i] > wt:
                K[i][wt] = K[i-1][wt]
            else:
                K[i][wt] = max(K[i-1][wt], v[i] + K[i-1][wt - w[i]])

    return K[n][W]

Время: \(\Theta(nW)\) — псевдополиномиально (pseudo-polynomial) по величине \(W\).

Память: \(\Theta(nW)\).

Замечание про сложность: время зависит от числового значения \(W\), а не только от числа предметов \(n\). Если \(W\) астрономическое (например, \(2^{100}\)), таблица по \(W\) станет неподъёмной при «маленьком» с виду входе в битах.

1.8 Divide and conquer и DP: сравнение

Оба подхода дробят задачу на подзадачи, но критично различаются пересечением работы:

Аспект Divide and conquer Dynamic programming
Пересечение подзадач Подзадачи независимы Подзадачи перекрываются
Когда уместно Каждая подзадача считается один раз в своей ветке Одна и та же подзадача нужна во многих ветках
Реализация Прямая рекурсия Tabulation или memoization
Примеры Merge sort, quicksort, binary search Фибоначчи, LCS, knapsack, rod cutting
Память В основном стек рекурсии Хранение ответов на подзадачи

Смысл: если в дереве рекурсии вы снова и снова встречаете одинаковые подзадачи, DP с запоминанием ответов обычно устраняет лишнюю работу.

2. Определения

  • Dynamic Programming (DP): приём решения задач оптимизации через перекрывающиеся подзадачи с однократным вычислением и запоминанием результатов.
  • Optimization problem: задача с множеством кандидатов, у каждого — числовое значение; нужен кандидат с оптимальным (min/max) значением.
  • Optimal substructure: оптимум целого строится из оптимумов частей.
  • Overlapping subproblems: при рекурсии одни и те же подзадачи возникают многократно.
  • Bottom-up (tabulation): DP снизу вверх заполнением таблицы.
  • Top-down (memoization): DP сверху вниз с кэшем на рекурсии.
  • Memoization: сохранение результатов дорогих вызовов и возврат из кэша при повторе аргументов.
  • Subsequence: последовательность после удаления части элементов без смены порядка остальных.
  • Common subsequence: общая подпоследовательность двух (или более) последовательностей.
  • Longest Common Subsequence (LCS): самая длинная общая подпоследовательность двух последовательностей.
  • Maximum subarray: непрерывный подотрезок с максимальной суммой.
  • Kadane’s algorithm: алгоритм за \(O(n)\) для maximum subarray на идее DP.
  • Rod cutting problem: максимизация выручки при разрезании стержня по таблице цен.
  • 0–1 knapsack problem: максимизация ценности при весе \(\le W\), каждый предмет не более одного раза.
  • Pseudo-polynomial time: время полиномиально по величине чисел во входе, но экспоненциально по числу битов.

3. Формулы

  • Рекуррентность Фибоначчи: \(F_n = F_{n-1} + F_{n-2}\), \(F_0 = 0\), \(F_1 = 1\)
  • Время наивной рекурсии Фибоначчи: \(T(n) = \Theta(\phi^n)\), \(\phi = \frac{1+\sqrt{5}}{2} \approx 1.618\)
  • Время DP для Фибоначчи: \(\Theta(n)\)
  • Золотое сечение: \(\phi = \frac{1+\sqrt{5}}{2}\)
  • maxSuffixValue: \(\text{maxSuffixValue}(A, i) = \begin{cases} A[1], & \text{if } i = 1 \\ \max(\text{maxSuffixValue}(A, i-1) + A[i], A[i]), & \text{otherwise} \end{cases}\)
  • Время Кадане: \(\Theta(n)\)
  • Рекуррентность LCS: \(\text{LCS}'(X_m, Y_n) = \begin{cases} 0, & \text{if } m = 0 \text{ or } n = 0 \\ 1 + \text{LCS}'(X_{m-1}, Y_{n-1}), & \text{if } x_m = y_n \\ \max(\text{LCS}'(X_{m-1}, Y_n), \text{LCS}'(X_m, Y_{n-1})), & \text{otherwise} \end{cases}\)
  • Время LCS: \(\Theta(mn)\) при \(m = |X|\), \(n = |Y|\)
  • Память LCS: \(\Theta(mn)\)
  • Rod cutting: \(r_n = \max_{1 \le i \le n} (p_i + r_{n-i})\), \(r_0 = 0\)
  • Время rod cutting: \(\Theta(n^2)\)
  • Knapsack: \(K(i, w) = \begin{cases} 0, & \text{if } i = 0 \text{ or } w = 0 \\ K(i-1, w), & \text{if } w_i > w \\ \max(K(i-1, w), v_i + K(i-1, w - w_i)), & \text{otherwise} \end{cases}\)
  • Время knapsack: \(\Theta(nW)\) (pseudo-polynomial)
  • Память knapsack: \(\Theta(nW)\)

4. Примеры

4.1. Назначение разработчиков на проекты (Набор задач 5, Задание 1)

Компании нужно сдать \(S\) проектов за квартал. Есть \(D\) разработчиков; каждый не более чем на одном проекте весь квартал (на один проект можно поставить нескольких). Цель — минимизировать суммарное время завершения всех проектов.

Оценки времени завершения проекта в зависимости от числа назначенных разработчиков даны в таблице \(C\), где \(C[\text{project}][\text{devs}]\) — срок в днях.

(1a)(i) Как выразить оптимальное решение через оптимальные решения подзадач, которые можно считать «независимо» в смысле DP? На конкретном примере покажите, что наивная рекурсия повторно пересчитывает одни и те же подзадачи.

(1b) Псевдокод DP (top-down или bottom-up), который возвращает и минимальную суммарную длительность, и конкретное распределение разработчиков по проектам.

(2) Рассмотрите жадную стратегию: проекты по порядку A, B, C, D, E; для каждого проекта выбирается число разработчиков, минимизирующее срок именно этого проекта при оставшихся людях; затем переход к следующему. Докажите, что это не всегда оптимально: (i) маленький контрпример, (ii) жадное назначение и суммарное время, (iii) оптимальное назначение и время, (iv) кратко, почему жадный шаг ошибается глобально.

(3) Асимптотика в худшем случае для: (a) наивной рекурсии, (b) DP-алгоритма.

(4) Примените эффективный алгоритм к таблице ниже при \(D = 8\), \(S = 5\): таблица оптимумов для всех подзадач и итоговый ответ.

Число разработчиков 0 1 2 3 4 5 6 7 8
Проект A \(\infty\) 24 d 21 d 18 d 14 d 9 d 9 d 8 d 7 d
Проект B \(\infty\) 28 d 22 d 20 d 16 d 11 d 10 d 10 d 9 d
Проект C \(\infty\) 38 d 31 d 30 d 24 d 20 d 18 d 14 d 13 d
Проект D \(\infty\) 34 d 33 d 22 d 20 d 16 d 14 d 12 d 11 d
Проект E \(\infty\) 32 d 26 d 21 d 17 d 13 d 11 d 10 d 9 d
Нажмите, чтобы увидеть решение

Ключевая идея: классическое DP-распределение \(D\) разработчиков по \(S\) проектам. Здесь минимизируется сумма сроков: выбрать \(d_i\) на проект \(i\) так, что \(\sum d_i = D\) и \(\sum C[i][d_i]\) минимально.

1(a)(i) Оптимальная подструктура:

Пусть \(\text{opt}(k, d)\) — минимальная суммарная длительность по первым \(k\) проектам при ровно \(d\) разработчиках. Тогда

\[\text{opt}(k, d) = \min_{0 \le j \le d} \bigl(\text{opt}(k-1,\, d - j) + C[k][j]\bigr)\]

с базой \(\text{opt}(0, d) = 0\) для всех \(d\) (нет проектов — нет вклада) и \(\text{opt}(k, 0) = \infty\) при \(k \ge 1\) (нельзя оставить проект без людей).

Наивная рекурсия многократно запрашивает один и тот же \(\text{opt}(k, d)\) из разных «родителей»: например, \(\text{opt}(2, 3)\) нужен и при разборе \(\text{opt}(3, 5)\) с одним \(j\), и при других ветках с иными \(j\).

1(b) Псевдокод (bottom-up DP):

function ASSIGN-DEVELOPERS(S, D, C):
    // dp[k][d] = min total time for first k projects with d developers
    dp[0..S][0..D] ← ∞
    dp[0][d] ← 0 for all d
    assign[k][d] ← 0  // stores how many devs assigned to project k

    for k ← 1 to S:
        for d ← 0 to D:
            for j ← 0 to d:
                if C[k][j] + dp[k-1][d-j] < dp[k][d]:
                    dp[k][d] ← C[k][j] + dp[k-1][d-j]
                    assign[k][d] ← j

    // Reconstruct assignment
    remaining ← D
    for k ← S downto 1:
        devs[k] ← assign[k][remaining]
        remaining ← remaining - devs[k]

    return dp[S][D], devs

2. Контрпример к жадному:

Возьмём 2 разработчика и 2 проекта с \(C[A][0] = C[B][0] = \infty\), \(C[A][1] = C[B][1] = 5\), \(C[A][2] = C[B][2] = 1\).

  • (i) Маленькая таблица выше.
  • (ii) Жадный порядок A, B: на A нельзя взять 2 человек (B останется без людей), значит на A берём 1 (5 дней), на B — 1 (5 дней), сумма 10.
  • (iii) Оптимум: в этом симметричном примере тоже 10 при \((1,1)\); чтобы показать строгое отличие жадного от глобального оптимума, нужна несимметричная таблица, где локальный минимум по текущему проекту «съедает» людей, нужных дальше по списку.
  • (iv) Жадный шаг смотрит только на стоимость текущего проекта и не моделирует, как остаток разработчиков повлияет на будущие строки \(C\); локально лучшее число людей на раннем проекте может удорожить сумму по всем.

3. Сложность:

  • (a) Наивная рекурсия: до \(S\) уровней ветвления и до \((D+1)\) вариантов на уровень — порядок \(O((D+1)^S)\) вызовов в худшем случае, экспоненциально по \(S\).
  • (b) DP: состояний \(O(S \cdot D)\), на состояние перебор \(j\) до \(d\) — суммарно \(\Theta(S \cdot D^2)\) времени и \(\Theta(S \cdot D)\) памяти.

4. Применение к таблице (\(D = 8\), \(S = 5\)):

Считаем \(\text{opt}(k, d)\) для \(k = 1 \ldots 5\), \(d = 0 \ldots 8\).

После \(k = 1\) (только проект A):

\(d\) 0 1 2 3 4 5 6 7 8
\(\text{opt}(1,d)\) \(\infty\) 24 21 18 14 9 9 8 7
assign A — 1 2 3 4 5 6 7 8

Для следующих проектов перебираются все разбиения \(d\) между новым проектом и уже учтённым префиксом; оптимальные сплиты накапливаются в таблице.

Итог по всем 8 разработчикам и 5 проектам:

Чтобы найти минимум, перечисляются допустимые распределения с \(\sum d_i = 8\), \(d_i \ge 1\), и минимизируется \(\sum C[i][d_i]\):

  • A=1(24), B=1(28), C=1(38), D=1(34), E=4(17): сумма 141 — слишком много проектов с одним разработчиком
  • A=2(21), B=2(22), C=1(38), D=1(34), E=2(26): devs = 8, сумма 141
  • A=3(18), B=2(22), C=1(38), D=1(34), E=1(32): devs = 8, сумма 144
  • A=2(21), B=1(28), C=2(31), D=1(34), E=2(26): devs = 8, сумма 140
  • A=1(24), B=2(22), C=2(31), D=1(34), E=2(26): devs = 8, сумма 137
  • A=2(21), B=2(22), C=2(31), D=1(34), E=1(32): devs = 8, сумма 140
  • A=1(24), B=2(22), C=1(38), D=2(33), E=2(26): devs = 8, сумма 143
  • A=2(21), B=1(28), C=1(38), D=2(33), E=2(26): devs = 8, сумма 146
  • A=1(24), B=2(22), C=2(31), D=2(33), E=1(32): devs = 8, сумма 142
  • A=2(21), B=2(22), C=2(31), D=2(33), E=0: невозможно (проекту E нужен ≥1)
  • A=1(24), B=1(28), C=2(31), D=2(33), E=2(26): devs = 8, сумма 142
  • A=2(21), B=1(28), C=2(31), D=2(33), E=1(32): devs = 8, сумма 145
  • A=1(24), B=2(22), C=3(30), D=1(34), E=1(32): devs = 8, сумма 142
  • A=2(21), B=2(22), C=1(38), D=2(33), E=1(32): devs = 8, сумма 146
  • A=1(24), B=3(20), C=2(31), D=1(34), E=1(32): devs = 8, сумма 141
  • A=2(21), B=3(20), C=1(38), D=1(34), E=1(32): devs = 8, сумма 145
  • A=1(24), B=3(20), C=1(38), D=2(33), E=1(32): devs = 8, сумма 147
  • A=3(18), B=1(28), C=2(31), D=1(34), E=1(32): devs = 8, сумма 143
  • A=1(24), B=2(22), C=3(30), D=2(33), E=0: невозможно
  • A=2(21), B=2(22), C=3(30), D=1(34), E=0: невозможно
  • A=1(24), B=1(28), C=3(30), D=2(33), E=1(32): devs = 8, сумма 147
  • A=2(21), B=1(28), C=3(30), D=1(34), E=1(32): devs = 8, сумма 145
  • A=3(18), B=2(22), C=2(31), D=1(34), E=0: невозможно
  • A=1(24), B=2(22), C=2(31), D=1(34), E=2(26): devs = 8, сумма 137 ← кандидат

DP находит глобальный оптимум. Минимальная суммарная длительность — 137 дней, в том числе так:

  • A: 1 разработчик → 24 дня
  • B: 2 → 22 дня
  • C: 2 → 31 день
  • D: 1 → 34 дня
  • E: 2 → 26 дней
  • Итого людей: \(1+2+2+1+2=8\); сумма: \(24+22+31+34+26=137\)

Ответ: минимум 137 дней, назначение A=1, B=2, C=2, D=1, E=2.

4.2. Вычислить \(F_6\) наивной рекурсией (Лекция 5, Пример 1)

Найдите \(F_6\) наивным рекурсивным алгоритмом. Сколько всего делается вызовов функции?

Нажмите, чтобы увидеть решение

Ключевая идея: проследить дерево вызовов и увидеть массовое дублирование работы.

Рекурсивное определение:

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) for n ≥ 2

Фрагмент дерева для F(6):

                    F(6)
                   /    \
              F(5)      F(4)
             /   \      /   \
        F(4)   F(3)  F(3)  F(2)
        / \    / \    / \   / \
      F(3) F(2) F(2) F(1) F(2) F(1) F(1) F(0)
      ...  (continues with more branches)

Сколько раз вызывается каждое значение (типичный подсчёт по дереву):

  • \(F(0)\): 5 раз
  • \(F(1)\): 8 раз
  • \(F(2)\): 5 раз
  • \(F(3)\): 3 раза
  • \(F(4)\): 2 раза
  • \(F(5)\): 1 раз
  • \(F(6)\): 1 раз

Суммарно вызовов: при полной трассировке наивной рекурсии для \(F(6)\) получается 25 вызовов функции (см. дерево вызовов; отдельные подсчёты по «типам» значений дают те же порядки повторного использования).

Точнее, число вызовов связано с \(T(n) = T(n-1) + T(n-2) + 1 \approx 2F_n - 1 = \Theta(\phi^n)\).

Ответ: вычисление \(F_6\) наивной рекурсией даёт 25 вызовов функции в стандартной трассировке; экспоненциальный рост делает наивный подход непригодным уже при умеренных \(n\).

4.3. Фибоначчи и bottom-up DP (Лекция 5, Пример 2)

Вычислите \(F_{10}\) bottom-up DP. Покажите таблицу.

Нажмите, чтобы увидеть решение

Ключевая идея: заполнить ряд значений от \(F_0\) вверх.

Таблица:

\(i\) 0 1 2 3 4 5 6 7 8 9 10
\(F_i\) 0 1 1 2 3 5 8 13 21 34 55

Шаги:

  1. Инициализация: \(F_0 = 0\), \(F_1 = 1\)
  2. Для \(i = 2,\ldots,10\): \(F_i = F_{i-1} + F_{i-2}\)
    • \(F_2 = 1\), \(F_3 = 2\), \(F_4 = 3\), \(F_5 = 5\), \(F_6 = 8\), \(F_7 = 13\), \(F_8 = 21\), \(F_9 = 34\), \(F_{10} = 55\)

Ответ: \(F_{10} = 55\); нужно всего 10 сложений по одному на новый индекс — вместо тысяч вызовов при наивной рекурсии.

4.4. Максимальный подмассив и Кадане (Лекция 5, Пример 3)

Найдите максимальный подотрезок для \(A = [-2, 1, -3, 4, -1, 2, 1, -5, 4]\) методом DP (Кадане).

Нажмите, чтобы увидеть решение

Ключевая идея: поддерживать лучшую сумму суффикса, заканчивающегося в \(i\), и глобальный максимум.

Трассировка:

\(i\) \(A[i]\) \(\text{max\_suffix\_sum}\) (до) \(\text{max\_suffix\_sum} + A[i]\) \(A[i]\) \(\text{max\_suffix\_sum}\) (после) \(\text{max\_sum}\)
1 -2 — — -2 -2 -2
2 1 -2 \(-2 + 1 = -1\) 1 1 ✓ 1
3 -3 1 \(1 + (-3) = -2\) -3 -2 1
4 4 -2 \(-2 + 4 = 2\) 4 4 ✓ 4
5 -1 4 \(4 + (-1) = 3\) ✓ -1 3 4
6 2 3 \(3 + 2 = 5\) ✓ 2 5 5
7 1 5 \(5 + 1 = 6\) ✓ 1 6 6
8 -5 6 \(6 + (-5) = 1\) ✓ -5 1 6
9 4 1 \(1 + 4 = 5\) ✓ 4 5 6

Пояснение:

  • В позиции 2 продолжение суффикса с 1 даёт \(-1\), новый старт в 2 даёт \(1\) — берём \(1\).
  • В позиции 4 выгоднее начать новый отрезок с \(4\), а не продолжать с \(-2\).
  • На участке 4–7 продолжение каждый раз не хуже нового старта.
  • Глобальный максимум \(6\) достигается в позиции 7.

Индексы: подотрезок \([4, -1, 2, 1]\) (позиции 4–7), сумма \(6\).

Ответ: максимальная сумма 6, индексы 4–7.

4.5. НОП (LCS) двух последовательностей (Лекция 5, Задание 1)

Примените алгоритм LCS к:

  • \(X = \langle A, B, C, B, D, A, B \rangle\)
  • \(Y = \langle B, D, C, A, B, A \rangle\)
Нажмите, чтобы увидеть решение

Ключевая идея: таблица DP по всем парам префиксов \(X\) и \(Y\).

Таблица \(C[i, j]\):

\(j=0\) B D C A B A
\(i=0\) 0 0 0 0 0 0 0
A 0 0 0 0 1 1 1
B 0 1 1 1 1 2 2
C 0 1 1 2 2 2 2
B 0 1 1 2 2 3 3
D 0 1 2 2 2 3 3
A 0 1 2 2 3 3 4
B 0 1 2 2 3 4 4

Восстановление: от \(C[7, 6] = 4\) идти по стрелкам назад:

  • \((7, 6)\): \(B = B\), диагональ → взять B
  • \((6, 5)\): \(A = A\), диагональ → взять A
  • \((5, 4)\): \(D \neq A\), переход слева или сверху
  • далее аналогично…

Одна из НОП: \(\langle B, C, A, B \rangle\), длина 4.

Ответ: длина НОП равна 4; пример НОП — \(\langle B, C, A, B \rangle\).

4.6. Rod cutting (Лекция 5, Задание 2)

Примените алгоритм rod cutting к стержню длины \(n = 10\) с ценами:

Длина \(i\) 1 2 3 4 5 6 7 8 9 10
Цена \(p[i]\) 1 5 8 9 10 17 17 20 24 30

Заполните строку оптимальных выручек \(r[i]\) для каждой длины \(i\).

Нажмите, чтобы увидеть решение

Ключевая идея: для каждой длины перебрать все варианты «первого куска» и взять максимум.

Таблица \(r[i]\):

Длина \(i\) 0 1 2 3 4 5 6 7 8 9 10
Выручка \(r[i]\) 0 1 5 8 10 13 17 18 22 25 30

Пошаговый расчёт:

  1. \(i = 1\): \(r[1] = 1\)
  2. \(i = 2\): \(\max(1+1,\,5+0)=5\)
  3. \(i = 3\): \(\max(1+5,\,5+1,\,8+0)=8\)
  4. \(i = 4\): \(\max(9,10,9,9)=10\)
  5. \(i = 5\): \(13\)
  6. \(i = 6\): \(17\)
  7. \(i = 7\): \(18\)
  8. \(i = 8\): \(22\)
  9. \(i = 9\): \(25\)
  10. \(i = 10\): \(30\) (оптимально не резать)

Ответ: \(r[10]=30\); один из оптимумов — продать целиком за \(30\).

4.7. Рюкзак 0–1 (Лекция 5, Задание 3)

Заполните идею DP-таблицы \(K[i,w]\) для вместимости \(W = 24\) кг и предметов:

Предмет 1 2 3 4 5 6 7
Вес (кг) 12 2 6 3 24 1 9
Ценность ($) 36 4 24 2 64 1 22
Нажмите, чтобы увидеть решение

Ключевая идея: \(K[i, w]\) — максимальная ценность по первым \(i\) предметам при лимите веса \(w\).

Разбор при \(W = 24\):

  • Предмет 5 (палатка, tent) весит ровно 24 кг и даёт ценность \(64\).
  • Любая другая комбинация из таблицы не превосходит \(64\) (например, \(1+3+6\): вес 19 кг, ценность \(61\); \(1+7+6\): 22 кг, \(59\)).

Ответ: максимум $64 — взять только предмет 5.

4.8. Сравнить реализации Фибоначчи (Лекция 5, Задание 4)

Сравните число операций для \(F_{20}\) при:

  1. наивной рекурсии
  2. мемоизации
  3. bottom-up DP
Нажмите, чтобы увидеть решение

Ключевая идея: сравнить число сложений и/или вызовов.

(a) Наивная рекурсия:

  • Вызовов порядка \(T(n) \approx 2F_n - 1\)
  • При \(n = 20\): \(F_{20} = 6765\), значит около \(2 \cdot 6765 - 1 = 13\,529\) вызовов
  • Сложений: порядка \(6\,765\)

(b) Мемоизация:

  • Каждое из \(F_0,\ldots,F_{20}\) вычисляется один раз
  • Вызовов функции: порядка \(n+1 = 21\)
  • Сложений: \(n-1 = 19\)
  • Итого: порядка 21 обращений к кэшу + 19 сложений \(\approx 40\) элементарных шагов в такой модели

(c) Bottom-up DP:

  • Цикл \(i = 2,\ldots,20\): 19 итераций, по одному сложению
  • Итого: 19 сложений

Сравнение:

Метод Вызовы Сложения Порядок
Наивная рекурсия ~13 529 ~6 765 \(O(2^n)\)
Мемоизация 21 19 \(O(n)\)
Bottom-up DP 0 рекурсии 19 \(O(n)\)

Ответ: по числу сложений выигрывает bottom-up (19); наивная рекурсия экспоненциально медленнее.

4.9. Rod cutting со стоимостью реза (Лекция 5, Задание 5)

Модификация: каждый разрез стоит \(c\) долларов. Как меняется рекуррентность?

Нажмите, чтобы увидеть решение

Ключевая идея: из выручки при каждом реальном разрезе вычитается \(c\).

Если делаем разрез:

  • выручка за первый кусок: \(p_i\)
  • за остаток: \(r_{n-i}\)
  • плюс штраф \(-c\) за сам разрез

Тогда

\[r_n = \max\begin{cases} p_n & \text{(no cut)} \\ \max_{1 \le i < n} (p_i + r_{n-i} - c) & \text{(make a cut)} \end{cases}\]

Эквивалентно:

\[r_n = \max\left(p_n, \max_{1 \le i < n} (p_i + r_{n-i} - c)\right)\]

Отличие: при большом \(c\) может быть выгоднее резать реже или не резать вовсе.

Пример: \(n = 4\), \(p = [1, 5, 8, 9]\), \(c = 2\): без разреза \(9\); с разрезами выигрыш меньше после вычитания \(c\).

Ответ: в рекуррентность входит вычитание \(c\) на каждый сделанный разрез: \(r_n = \max(p_n, \max_{1 \le i < n}(p_i + r_{n-i} - c))\).