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

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

С научно-алгоритмической точки зрения динамическое программирование представляет собой один из важнейших методов дискретной оптимизации и вычислительной информатики. Его применение охватывает задачи поиска кратчайших путей, оптимального разбиения, обработки последовательностей, подсчёта числа способов, работы с графами, строками, массивами и комбинаторными структурами. Для подготовки к ЕГЭ по информатике эта тема имеет принципиальное значение, поскольку связывает воедино сразу несколько базовых разделов: рекурсию, циклы, массивы, табличные вычисления, асимптотический анализ, инварианты корректности и логическое моделирование состояний.

Ниже представлен системный и очень подробный разбор темы: математическая и алгоритмическая модель динамического программирования, критерии применимости метода, правила выбора состояния и переходов, способы организации вычислений, доказательство корректности, оптимизация памяти, типичные ошибки, мини-шпаргалка и пять упражнений, ориентированных на формат и компетенции ЕГЭ по информатике.

Формальная модель динамического программирования

1. Общая идея метода
   

   Пусть требуется вычислить значение целевой функции

   Ans = F(X)

   для некоторого входного объекта X. Метод динамического программирования применим, если задача допускает представление в виде семейства взаимосвязанных подзадач

   S = {s_1, s_2, ..., s_m},

   таких, что:

   1. ответ для исходной задачи выражается через ответы для некоторых подзадач; 

   2. множество возможных подзадач конечно и не слишком велико; 

   3. разные ветви решения многократно обращаются к одним и тем же подзадачам; 

   4. для каждой подзадачи можно задать рекуррентное правило перехода. 

   В такой ситуации вводится таблица значений

   dp[state]

   или, в многомерном случае,

   dp[i][j], dp[i][j][k], ...

   где state – формализованное описание подзадачи.

2. Компоненты динамической модели
   

   Полная модель динамического программирования включает пять обязательных компонентов:

   1. Состояние – параметризация подзадачи. 

   2. Базовые случаи – начальные значения, задаваемые без рекурсии. 

   3. Переход – формула вычисления текущего состояния через ранее посчитанные. 

   4. Порядок вычисления – топологически корректная последовательность заполнения таблицы. 

   5. Извлечение ответа – правило, по которому из таблицы получается итоговое значение. 

   В формальном виде:

   dp[s] = G( dp[s_1], dp[s_2], ..., dp[s_t], data )

   где s_1, ..., s_t – состояния, предшествующие s по зависимости.

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

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

   Это означает, что оптимальный ответ можно строить по частям, не опасаясь, что локально неoptimalьное решение приведёт к глобально лучшему результату. В символической форме:

   OPT(s) = best over decisions d of Combine( d, OPT(next(s, d)) )

   где OPT(s) – оптимальный ответ для состояния s.

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

1. Перекрывающиеся подзадачи
   Первое необходимое условие – наличие перекрывающихся подзадач. Если рекурсивное дерево вычислений содержит повторяющиеся узлы, динамическое программирование позволяет вычислить каждый такой узел только один раз.

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

   F(n) = F(n−1) + F(n−2),   F(0)=0, F(1)=1

   Наивная рекурсия для F(n) вычисляет F(n−2) дважды, F(n−3) трижды и так далее. Таблица dp[n] устраняет эту избыточность.

2. Оптимальная подструктура
   Второе условие – наличие оптимальной подструктуры. Если решение большой задачи можно получить из оптимальных решений меньших задач, метод применим. Если же глобально оптимальный ответ требует локально неоптимальных промежуточных выборов, прямое динамическое программирование может оказаться неприменимым или потребует иного состояния.

3. Конечность и управляемость пространства состояний
   Даже если подзадачи перекрываются, метод практически полезен только тогда, когда число различных состояний конечно и вычислимо. Если состояний слишком много, таблица становится слишком большой по времени или памяти.

Основные способы организации динамики

1. Мемоизация
   

   Мемоизация – это рекурсивный стиль, в котором функция вызывает саму себя, но результаты уже вычисленных состояний запоминаются в кэше.

   Схема:

   функция solve(state):
       если state уже вычислено:
           вернуть сохранённый ответ
       если state базовое:
           вернуть базовое значение
       вычислить answer через solve(другие состояния)
       сохранить answer
       вернуть answer

   Плюсы:

   • естественно отражает математическую рекурсию; 

   • легко реализуется для сложных переходов; 

   • вычисляются только реально нужные состояния. 

   Минусы:

   • накладные расходы на рекурсию; 

   • риск переполнения стека; 

   • иногда труднее контролировать порядок вычисления. 

2. Табуляция
   

   Табуляция – итерационный стиль, при котором состояния вычисляются в заранее заданном порядке.

   Схема:

   инициализировать базовые состояния
   для state в корректном порядке:
       вычислить dp[state] через уже известные значения
   вернуть итоговый ответ

   Плюсы:

   • отсутствие рекурсивного стека; 

   • полный контроль над памятью; 

   • удобно анализировать асимптотику. 

   Минусы:

   • иногда приходится вычислять состояния, которые в итоге не нужны; 

   • нужно заранее понять правильный порядок заполнения. 

3. Сравнение мемоизации и табуляции
   

   Обе стратегии реализуют один и тот же математический принцип. Выбор зависит от структуры задачи. В задачах ЕГЭ чаще всего удобнее табуляция, поскольку она лучше согласуется с циклами и массивами, традиционно используемыми в экзаменационных решениях.

Как правильно строить состояние

1. Принцип достаточности состояния
   

   Состояние должно содержать ровно ту информацию, которая нужна для продолжения вычисления. Недостаточное состояние приводит к потере информации и некорректным переходам. Избыточное – к неэффективности.

   Формально состояние должно быть таким, чтобы:

   будущее поведение задачи зависело только от state,
   а не от всей предыстории.

2. Примеры состояний
   

   1. Для Фибоначчи:
      dp[i] = F(i)

   2. Для задачи «минимальная стоимость пути до клетки (i,j)»:
      dp[i][j] = минимальная стоимость попасть в клетку (i,j)

   3. Для задачи о рюкзаке:
      dp[i][w] = максимальная стоимость, которую можно получить, рассматривая первые i предметов и имея ограничение веса w

   4. Для строковых задач:
      dp[i][j] = ответ для первых i символов первой строки и первых j символов второй

3. Правило выбора параметров
   

   При выборе параметров состояния полезно задавать себе вопрос:

   «Если я нахожусь в этом состоянии, достаточно ли этих параметров, чтобы однозначно описать все будущие решения?»

   Если ответ отрицательный, состояние надо расширять.

Базовые случаи и их роль

1. Почему база обязательна
   Без базовых значений рекуррентная формула не имеет точки опоры. Таблица динамики должна начинаться с минимальных подзадач, ответы для которых известны непосредственно.

2. Формальная роль базы
   Пусть переход задан формулой:

   dp[s] = G(dp[s_1], ..., dp[s_t])

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

3. Примеры
   

   1. Фибоначчи: 

   dp[0] =0

   dp[1] = 1

   2. Пути по таблице: 

   dp[1][1]= cost[1][1]

   3. Наибольшая общая подпоследовательность: 

   dp[0][j]= 0

   dp[i][0] = 0

Переходы и рекуррентные соотношения

1. Природа перехода
   

   Переход выражает текущий ответ через уже известные. В задачах оптимизации переход часто имеет вид:

   dp[state] = min(...)

   или

   dp[state] = max(...)

   В задачах подсчёта:

   dp[state] = sum(...)

2. Типы переходов
   

   1. Аддитивные: сумма количества способов. 

   2. Оптимизационные: минимум/максимум. 

   3. Булевы: достижимость, существование. 

   4. Комбинированные: пара «значение + восстановление решения».

3.  Корректность перехода
   

   Чтобы рекуррентное соотношение было корректным, нужно показать два факта:

   1. Любое решение, учитываемое формулой, действительно допустимо. 

   2. Любое допустимое оптимальное решение попадает в рассмотрение формулы. 

   Только сочетание этих двух пунктов гарантирует корректность.

Порядок вычисления и инварианты заполнения таблицы

1. Топологический принцип
   Если dp[s] зависит от dp[s'], то s' должно быть вычислено раньше s. Поэтому порядок заполнения таблицы обязан уважать граф зависимостей.

2. Инвариант заполнения
   Типичный инвариант:
   к началу вычисления строки i (или столбца j) все состояния, от которых зависят значения этой строки, уже корректно посчитаны.

3.  Пример
   Для формулы
   dp[i][j] = min(dp[i−1][j], dp[i][j−1]) + cost[i][j]
   достаточно идти по таблице сверху вниз и слева направо, потому что состояния (i−1,j) и (i,j−1) уже будут известны.

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

1. Числа Фибоначчи
   

   Рекуррент:

   dp[0] = 0
   dp[1] = 1
   dp[i] = dp[i−1] + dp[i−2],   i ≥ 2

   Сложность: O(n) времени, O(n) памяти.
   С оптимизацией памяти:

   храним только два последних значения → O(1) памяти

2. Количество способов подняться по лестнице
   

   Если можно подниматься на 1 или 2 ступени:

   dp[0] = 1
   dp[1] = 1
   dp[i] = dp[i−1] + dp[i−2]

   Смысл другой, рекуррент тот же.

3. Минимальная стоимость пути по таблице
   

   Пусть можно идти только вправо и вниз:

   dp[1][1] = a[1][1]
   dp[i][1] = dp[i−1][1] + a[i][1]
   dp[1][j] = dp[1][j−1] + a[1][j]
   dp[i][j] = min(dp[i−1][j], dp[i][j−1]) + a[i][j]

4. Задача о рюкзаке 0/1
   

   Пусть предметы имеют веса w[i] и стоимости c[i], вместимость рюкзака W.

   dp[i][x] = максимальная стоимость при использовании первых i предметов и вместимости x

   Переход:

   dp[i][x] = dp[i−1][x],                        если w[i] > x
   dp[i][x] = max(dp[i−1][x], dp[i−1][x−w[i]] + c[i]), иначе

5. Наибольшая общая подпоследовательность
   

   Для строк A и B:

   dp[i][j] = длина НОП для префиксов A[1..i], B[1..j]

   Переход:

   если A[i] = B[j], то dp[i][j] = dp[i−1][j−1] + 1
   иначе dp[i][j] = max(dp[i−1][j], dp[i][j−1])

Мини-шпаргалка по динамическому программированию

1. Универсальный шаблон
   1. Определить состояние dp[...]
   2. Задать базовые случаи
   3. Выписать переход
   4. Определить порядок заполнения
   5. Получить ответ
   6. При необходимости восстановить решение
   

Связь с подготовкой к ЕГЭ по информатике

Динамическое программирование занимает особое место в структуре заданий повышенного уровня сложности ЕГЭ, поскольку требует не только знания алгоритмов, но и умения самостоятельно конструировать модель решения. В продолжение ранее изложенных положений необходимо подчеркнуть следующие аспекты:

• Формализация задачи через состояние: в заданиях ЕГЭ часто не дано явного указания на применение динамического программирования, однако наличие перекрывающихся подзадач и оптимизационного критерия (минимум/максимум/количество способов) служит прямым индикатором необходимости построения DP-модели. 

• Умение выводить рекуррентные соотношения: экзаменационные задания проверяют способность учащегося не воспроизводить известный алгоритм, а выводить переходы самостоятельно, исходя из структуры задачи. 

• Работа с таблицами и индексами: особое внимание уделяется правильному заполнению таблиц, корректному выбору диапазонов и индексации (с нуля или с единицы). 

• Анализ сложности: учащийся должен уметь обосновать, почему решение работает за O(n), O(n^2) или O(n log n), а также предложить оптимизацию. 

• Переход от псевдокода к реализации: часто требуется перевести логическую схему DP в конкретный язык программирования (например, Python или Pascal).

Пять упражнений 

Упражнение 1. Минимальная стоимость пути в таблице
Условие. Дана матрица n × m, в каждой клетке записано число. Разрешено двигаться только вправо или вниз. Найдите минимальную сумму пути из (1,1) в (n,m).
Решение (псевдокод):

dp[1][1] ← A[1][1]
для i от 2 до n делай
    dp[i][1] ← dp[i−1][1] + A[i][1]
все
для j от 2 до m делай
    dp[1][j] ← dp[1][j−1] + A[1][j]
все
для i от 2 до n делай
    для j от 2 до m делай
        dp[i][j] ← min(dp[i−1][j], dp[i][j−1]) + A[i][j]
    все
все
ответ ← dp[n][m]

Анализ:
Сложность O(n·m), память O(n·m) (можно оптимизировать до O(m)).

Упражнение 2. Количество способов дойти до клетки
Условие. Аналогично предыдущей задаче, но требуется найти количество различных путей.
Решение:

dp[1][1] ← 1
для i от 1 до n делай
    для j от 1 до m делай
        если i > 1 то dp[i][j] ← dp[i][j] + dp[i−1][j]
        если j > 1 то dp[i][j] ← dp[i][j] + dp[i][j−1]
    все
всеИнвариант:

dp[i][j] – число способов попасть в клетку (i,j). 

Упражнение 3. Наибольшая возрастающая подпоследовательность (LIS)
Условие. Найдите длину LIS.
Решение (O(n^2)):

для i от 1 до n делай
    dp[i] ← 1
    для j от 1 до i−1 делай
        если A[j] < A[i] то
            dp[i] ← max(dp[i], dp[j] + 1)
        все
    все
все
ответ ← max(dp[i]) 

Упражнение 4. Рюкзак (0/1)
Условие. Даны веса w[i] и стоимости v[i], вместимость W. Найти максимальную стоимость.
Решение:

для i от 0 до n делай
    для j от 0 до W делай
        dp[i][j] ← 0
    все
все
для i от 1 до n делай
    для j от 0 до W делай
        dp[i][j] ← dp[i−1][j]
        если j ≥ w[i] то
            dp[i][j] ← max(dp[i][j], dp[i−1][j−w[i]] + v[i])
        все
    все
все

Упражнение 5. Фибоначчи с мемоизацией
Условие. Реализуйте вычисление числа Фибоначчи с запоминанием.
Решение:

функция fib(n)
    если n ≤ 1 то вернуть n
    если dp[n] ≠ −1 то вернуть dp[n]
    dp[n] ← fib(n−1) + fib(n−2)
    вернуть dp[n]
конец

Сложность: O(n) вместо O(2^n).

Практические рекомендации 

• Всегда начинайте с простого перебора, затем оптимизируйте его через DP. 

• Чётко определяйте:

что хранит dp[i] или dp[i][j]

• Проверяйте: 

• базовые случаи; 

• корректность переходов; 

• границы массивов. 

• Используйте табличную запись, если рекурсия сложна для анализа. 

Итог

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

С методологической точки зрения ключевыми элементами являются:

• корректный выбор состояния; 
• формирование рекуррентного соотношения; 
• строгая проверка инвариантов; 
• обеспечение завершимости и оптимальности. 

В контексте подготовки к ЕГЭ владение динамическим программированием обеспечивает:

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

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