Открыть список
Как стать автором
Обновить
32
Карма
0
Рейтинг
Алексей Казимиров @cybrid

Пользователь

Динамическое программирование. Классические задачи

Алгоритмы
Из песочницы
Здравствуй, Хабрахабр. В настоящий момент я работаю над учебным пособием по олимпиадному программированию, один из параграфов которого посвящен динамическому программированию. Ниже приведена выдержка из данного параграфа. Пытаясь объяснить данную тему как можно проще, я постарался сложные моменты сопроводить иллюстрациями. Мне интересно ваше мнение о том, насколько понятным получился данный материал. Также буду рад советам, какие еще задачи стоит включить в данный раздел.

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

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

Такие задачи решают методом динамического программирования, а под самим динамическим программированием понимают сведение задачи к подзадачам.
Читать дальше →
Всего голосов 105: ↑97 и ↓8 +89
Просмотры255.1K
Комментарии 72

Информация

В рейтинге
5,789-й
Откуда
Иркутск, Иркутская обл., Россия
Дата рождения
Зарегистрирован
Активность