3.16 Динамическое программирование как метод решения задач с сохранением промежуточных результатов. Задачи, решаемые с помощью динамического программирования: вычисление рекурсивных функций, подсчёт количества вариантов, задачи оптимизации — Подготовка к ЕГЭ/ОГЭ и сессии СПО и ВУЗы

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

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

Основная идея ДП — избежать избыточных вычислений, сохраняя промежуточные результаты в памяти для их повторного использования.

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

Задача разбивается на перекрывающиеся подзадачи
Решение сохраняется для повторного использования (мемоизация)
Используется восходящий подход (табличное заполнение)

Основные этапы решения задач ДП

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

Формулировка рекуррентного соотношения — как решение задачи выражается через решения подзадач

Инициализация базовых случаев — определить решения для самых простых подзадач

Определение порядка вычислений — выбрать последовательность заполнения таблицы

Вычисление и сохранение результатов — заполнить таблицу решений

Восстановление ответа — по сохранённым данным восстановить решение исходной задачи

Вычисление рекурсивных функций

Классический пример — вычисление чисел Фибоначчи.

\( F(n) = F(n-1) + F(n-2) \), где \( F(0) = 0, F(1) = 1 \)

Наивная рекурсия vs ДП подход

Рекурсивное решение имеет экспоненциальную сложность O(2ⁿ), тогда как ДП решение имеет линейную сложность O(n).

// Наивная рекурсия (медленно) function fib(n) { if (n <= 1) return n; return fib(n-1) + fib(n-2); }

// Динамическое программирование (быстро) function fibDP(n) { if (n <= 1) return n; let dp = new Array(n+1); dp[0] = 0; dp[1] = 1; for (let i = 2; i <= n; i++) { dp[i] = dp[i-1] + dp[i-2]; } return dp[n]; }

Таблица вычисления чисел Фибоначчи

n	F(n)
0	0
1	1
2	1
3	2
4	3
5	5
6	8

Каждое следующее число вычисляется на основе двух предыдущих

Подсчёт количества вариантов

Задачи, в которых требуется найти количество способов достичь цели при определенных условиях.

Пример: Сколькими способами можно добраться из клетки (1,1) до клетки (N,M), если двигаться можно только вправо и вниз?

\( dp[i][j] = dp[i-1][j] + dp[i][j-1] \)

Решение задачи о ходе ладьи

Таблица путей для сетки 4×4

i\j	1	2	3	4
1	1	1	1	1
2	1	2	3	4
3	1	3	6	10
4	1	4	10	20

Количество путей до клетки (4,4) = 20

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

В этих задачах мы ищем не просто количество способов, а оптимальное решение (минимум или максимум).

Задача о рюкзаке: Имеется рюкзак вместимостью W и n предметов с весами w_i и стоимостью c_i. Нужно maximize стоимость предметов в рюкзаке.

\( dp[i][j] = \max(dp[i-1][j], dp[i-1][j — w_i] + c_i) \)

Решение задачи о рюкзаке

Пример решения задачи о рюкзаке

Вместимость рюкзака W = 5, предметы: (вес=2, стоимость=3), (вес=3, стоимость=4), (вес=4, стоимость=5)

i\w	2	3	4	5
0	0	0	0	0
1	3	3	3	3
2	3	4	4	7
3	3	4	5	7

Максимальная стоимость предметов в рюкзаке = 7

Полезные советы для ЕГЭ

Внимательно читайте условие задачи и определяйте тип (подсчет, оптимизация)
Определите параметры, которые будут определять состояние
Четко сформулируйте рекуррентное соотношение
Не забудьте про базовые случаи
Определите порядок заполнения таблицы (снизу вверх)
Проверяйте граничные значения
Убедитесь, что ответ правильно восстанавливается

Динамическое программирование — мощный инструмент для решения широкого класса задач. Понимание его основ значительно повысит ваши шансы на успешную сдачу ЕГЭ по информатике!

Динамическое программирование в задачах ЕГЭ по информатике