Аннотация
Работа посвящена некоторым методическим аспектам динамического программирования и решению одной олимпиадной задачи с использованием динамического программирования.
ВВЕДЕНИЕ
Олимпиадные задачи по информатике отличаются тематическим разнообразием. Однако, можно выделить наиболее часто встречающиеся разделы информатики, по которым разрабатываются олимпиадные задачи. К ним можно отнести:
- перебор вариантов и методы его сокращения;
- динамическое программирование;
- комбинаторика;
- сортировка и поиск;
- обработка последовательностей;
- элементы вычислительной геометрии;
- алгоритмы на графах.
ОСНОВНАЯ ЧАСТЬ
Динамическое программирование - это способ решения сложных задач путем разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой, выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной.
Метод динамического программирования сверху - это простое запоминание результатов решения тех подзадач, которые могут повторно встретиться в дальнейшем. Динамическое программирование снизу включает в себя переформулирование сложной задачи в виде рекурсивной последовательности более простых подзадач.
Во многих олимпиадных задачах по программированию решение с помощью рекурсии или полного перебора требует выполнения очень большого числа операций. Попытка решить такие задачи, например, полным перебором, приводит к превышению времени выполнения.
Однако среди переборных и некоторых других задач можно выделить класс задач, обладающих одним хорошим свойством: имея решения некоторых подзадач (например, для меньшего числа п), можно практически без перебора найти решение исходной задачи.
Такие задачи решают методом динамического программирования, а под самим динамическим программированием понимают сведение задачи к подзадачам.
Чтобы успешно решить задачу динамикой нужно:
- Состояние динамики: параметры, однозначно задающие подзадачу.
- Значения начальных состояний.
- Переходы между состояниями: формула пересчёта.
- Порядок пересчёта.
- Положение ответа на задачу: иногда это сумма или, например, максимум из значений нескольких состояний.
Порядок пересчёта
Существует три порядка пересчёта [1]:
1 Прямой порядок:
Состояния последовательно пересчитываются исходя из уже посчитанных.
- Обратный порядок:
Обновляются все состояния, зависящие от текущего состояния.
- Ленивая динамика:
Рекурсивная мемоизированная функция пересчёта динамики. Это что-то вроде поиска в глубину по ацикличному графу состояний, где рёбра - это зависимости между ними.
113
}
int main(){
int n;
cin>>n;
cout< <get_fib(n);
return 0;
}
Все три варианта имеют права на жизнь. Каждый из них имеет свою область применения, хотя часто пересекающуюся с другими.
Многомерная динамика. Она отличается от одномерной, количеством измерений, то есть количеством параметров в состоянии. Классификация по этому признаку обычно строится по схеме «один-два-много» и не особо принципиальна.
Многомерная динамика не сильно отличается от одномерной, в чём вы можно убедиться, взглянув на пару примеров:
Пример: Количество СМСок
Раньше, когда у телефонов были кнопки, их клавиатуры выглядели примерно так:
- Порядок пересчёта: если писать прямым методом, то надо отдельно подумать о выходе за границу динамики, к примеру, когда мы обращаемся к dp[n - l][m - 4], которого может не существовать при малых т. Для обхода этого можно или ставить проверки в пересчёте или записать туда нейтральные элементы (не изменяющие ответа).
114
При использовании обратного пересчёта всё проще: мы всегда обращаемся вперёд, так что в отрицательные элементы мы не уйдём.
- Ответ - это сумма всех состояний.
Задачу можно решить и одномерно, просто убрав из состояния длину сообщения п.
- Состояние: dp[m] - количество различных ености в, которые можно набрать за m нажатий.
- Начальное состояние: dp[O] = 1.
- Формула пересчёта:
dp[m]=(dp[m-l]+dp[m-2]+dp[m-3])*8+dp[m-4]*2;
- Порядок: все три варианта можно использовать.
- Ответ - это сумма всех состояний [3].
ЗАКЛЮЧЕНИЕ
Ключевая идея в динамическом программировании достаточно проста. Как правило, чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение. Часто многие из этих подзадач одинаковы. Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений. Это особенно полезно в случаях, когда число повторяющихся подзадач экспоненциально велико.
Список литературы
- Акулич И.Л. Задачи динамического программирования // Математическое программирование в примерах и задачах. -M.: Высшая школа, 1986. - 319 с.
- Красикова И.В. Динамическое программирование // Алгоритмы: построение и анализ. - M.: Вильямс, 2005. - 1296 с.
- Габасов P., Кириллова Ф.М. Основы динамического программирования. - Мн.: Изд-во БГУ, 1975. - 262 с.