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

С. М. Окулов, О. А. Пестов
ДИНАМИЧЕСКОЕ
ПРОГРАММИРОВАНИЕ
4-е издание, электронное
Москва
Лаборатория знаний
2024

УДК 519.85(023)
ББК 22.18
О-52
С е р и я
о с н о в а н а
в
2008 г.
Окулов С. М.
О-52
Динамическое
программирование
/
С. М. Окулов,
О. А. Пестов. — 4-е
изд.,
электрон. — М.
:
Лаборатория
знаний,
2024. — 299 с. — (Развитие
интеллекта
школьников). — Систем.
требования:
Adobe
Reader
XI
;
экран 10". — Загл. с титул. экрана. —
Текст : электронный.
ISBN 978-5-93208-702-2
В данной книге систематизирован материал по одному
из
методов
проектирования
алгоритмов
в
информатике —
динамическому
программированию.
Предлагаемые
задачи
решаются фактически по одной схеме, основанной на данном
методе, однако понять, что задача решается этим методом,
очень непросто. Для этого кроме знаний требуется усилие
подготовленного к решению таких задач интеллекта. Именно
этому способствуют содержание книги и стиль изложения
материала в ней.
Разобраны задачи, предлагавшиеся школьникам на всероссийских олимпиадах по информатике разных лет, а также
на турнирах и конкурсах.
Для учащихся старших классов, студентов и преподавателей информатики.
УДК 519.85(023)
ББК 22.18
Деривативное издание на основе печатного аналога: Динамическое программирование / С. М. Окулов, О. А. Пестов. —
М. : БИНОМ. Лаборатория знаний, 2012. — 296 с. : ил. —
(Развитие интеллекта школьников).
ISBN 978-5-9963-0483-7
В
соответствии
со
ст. 1299
и
1301
ГК
РФ
при
устранении
ограничений, установленных техническими средствами защиты
авторских прав, правообладатель вправе требовать от нарушителя
возмещения убытков или выплаты компенсации
ISBN 978-5-93208-702-2
© Лаборатория знаний, 2015

Оглавление
Вместо предисловия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Глава 1. Простые задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.1. Числа Фибоначчи . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2. Биномиальные коэффициенты, или Нахождение числа
сочетаний . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.3. Наибольший квадрат . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.4. Задача о Черепашке. . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Глава 2. Основной принцип и метод реализации на основе
рекуррентных соотношений. . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.1. Вводные замечания . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.2. Множество решаемых задач, вычисляемая функция
и рекуррентные соотношения . . . . . . . . . . . . . . . . . . . 35
2.3. Граф зависимостей задач . . . . . . . . . . . . . . . . . . . . . . . 38
2.4. Общая схема . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.5. Пример решения задачи . . . . . . . . . . . . . . . . . . . . . . . 45
Глава 3. Типы задач по динамическому
программированию . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.1. Табличный метод решения. . . . . . . . . . . . . . . . . . . . . . 49
3.2. Задачи на отрезках . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.3. Задачи на деревьях . . . . . . . . . . . . . . . . . . . . . . . . . . 106
3.4. Задачи на подмножествах . . . . . . . . . . . . . . . . . . . . . 140
3.5. Динамическое программирование по профилю . . . . . 156
Приложение I. Динамическое программирование
как метод решения задач оптимизации . . . . . . . . . . . . . . . . 201
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
1. Метод динамического программирования: основные
положения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
2. Примеры задач. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
2.1. Задача о распределении ресурсов . . . . . . . . . . . . . 209

Оглавление
2.2. Задача о рюкзаке . . . . . . . . . . . . . . . . . . . . . . . . . 226
2.3. Задачи о критических путях в графе . . . . . . . . . . 237
2.3.1. Перечисление путей в графе . . . . . . . . . . . . . . . . 238
2.3.2. Кратчайший путь в графе . . . . . . . . . . . . . . . . . . 241
2.3.3. Максимальный путь в графе . . . . . . . . . . . . . . . . 249
Приложение II. Справочные данные о задачах
динамического программирования. . . . . . . . . . . . . . . . . . . . 260

Вместо предисловия
Чиновники от образования все менее и менее
желают, чтобы молодежь становилась образованной. Их задача — не развивая умственных
способностей, просто сообщать информацию.
(Вероятно, именно с этим связано и увлечение
тестированием, так как именно усвоение информации легко и просто проверяется с помощью тестов.) В результате мы сталкиваемся
с тем парадоксальным фактом, что образование становится одним из основных препятствий к развитию интеллекта и свободе мысли.
Б. Рассел
Мы в своих книгах постоянно говорим об интеллекте, о
развитии интеллекта. Не слишком ли это претенциозно?
Возможно, мы вкладываем в данное понятие нечто другое, не
то, о чем говорят философы, психологи, и на основании нашего
определения рассуждаем об интеллекте. Действительно, например, в психологии достигнуты впечатляющие результаты. Помимо того что научились оценивать уровень развития интеллекта,
последний еще и классифицирован. «В науке известно 120 видов
интеллекта»1. Из наиболее часто встречающихся называют интеллект: физический, возрастной, чувственный, сексуальный,
творческий, социальный, личностный, духовный2. 120 видов интеллекта происходят из тестологической теории интеллекта. Но
она не единственная. Перечислим некоторые из теорий: теория
интеллекта Ж. Пиаже; культурно-историческая теория интеллекта Л. С. Выготского; процессуально-деятельностные теории
интеллекта (С. Л. Рубинштейн, П. Я. Гальперин, А. В. Брушлинский, Л. А. Венгер, О. К. Тихомирова); функционально-уровневые теории интеллекта (Б. Г. Ананьев, Б. М. Величковский);
регуляционные теории интеллекта (Л. Л. Терстоуном, Р. Стернберг) и т. д. Общим знаменателем перечисленных теорий является то, что они построены на индуктивных началах. Другими
1
Кинякина О. Н. и др. Мозг на 100%. Интеллект. Память. Креатив. Интуиция. Интенсив-тренинг по развитию суперспособностей. М.: Эксмо, 2009,
С. 75.
2
Там же. С. 75.

Вместо предисловия
словами, теоретические построения основаны на обобщении экспериментальных, практических результатов1.
Есть и другой путь — дедуктивный. Л. М. Веккер (онтологическая теория интеллекта) писал «о неправомерности описания психической реальности через совокупность её свойств»2.
М. А. Холодная говорит о структурно-интегративной методологии, которая «означает принципиальную смену исследовательской парадигмы, а именно: переход от описательного уровня
анализа свойств интеллекта, с высокой степенью вариативности
и разнообразия обнаруживающих себя в условиях тех или иных
«задачных» ситуаций, к объяснительному уровню анализа этих
свойств за счет выявления структурной организации интеллекта, по отношению к которым эти интеллектуальные свойства
выступают в качестве производных»3.
Итак, пусть мы придерживаемся дедуктивной схемы рассуждений. Но мало придерживаться, т. е. определить нечто
как интеллект, постулировать некие аксиомы и вывести логически свойства, особенности обозначенных явлений. Да, мы
можем определить интеллект, в первую очередь, как развитые
аналитические свойства ума. Но он состоит не только в этом, и
не будем торопиться. Например, после творческой проработки
материала данной книги у вас возникнет нечто, называемое
интуицией. При «встрече» с новой проблемой (задачей) вы будете уже интуитивно чувствовать, знать, решается она или нет
методом динамического программирования.
В соответствии с синергетической парадигмой мы определяем интеллект как сложную, открытую, самоорганизующуюся систему, развивающуюся по нелинейным законам (А). Не
будем пока обосновывать и раскрывать весь тот позитив, который уже дает такое понимание, а выстроим канву обоснования
исходного утверждения. Необходимым условием развития интеллекта является помещение интеллекта в среду, опять же
сложную, открытую, функционирующую по нелинейной динамике (В), но и это еще не всё. Деятельность интеллекта по
1
Индуктивные построения в любой науке должны быть, они содержат как
объяснительный, так и прогнозирующий потенциал.
2
Веккер Л. М. Психические процессы. Мышление и интеллект. Т. 2. Л.:
Изд-во Ленингр. ун-та, 1976.
3
Холодная М. А. Психология интеллекта. Парадоксы исследования. СПб.:
Питер, 2002. С. 81.

Вместо предисловия
7
«выживанию» в данной среде, в свою очередь, подчиняется тем
же законам — она сложна, открыта и нелинейна (С). Что мы
имеем в результате? В математике в этом случае говорят как
минимум о том, что есть взаимно однозначное соответствие
между A, B и C. Мы говорим о синергетической среде обучения
или среде по «произрастанию» интеллекта.
Обоснование и раскрытие положения А очень не просто.
Появление работ по философии, психологии, в полной мере доказывающих эту установку и показывающих, к чему она приводит, следует только приветствовать. Мы сошлемся на мысль
К. Майнцера1, который пишет: «Наш подход предполагает,
что физическая, социальная и ментальная реальность является нелинейной и сложной… Этот существенный результат синергетической
эпистемологии
влечет
за
собой
серьезные
следствия для нашего поведения. Стоит еще раз подчеркнуть,
что линейное мышление может быть опасным в нелинейной
сложной реальности… Наши врачи и психологи2 должны научиться рассматривать людей как сложных нелинейных существ, обладающих умом и телом. Линейное мышление может
терпеть неудачу в установлении правильных диагнозов… Мы
должны помнить, что в политике и истории монокаузальность
может вести к догматизму, отсутствию толерантности и фанатизму… Подход к изучению сложных систем порождает новые
следствия в эпистемологии и этике. Он дает шанс предотвратить хаос в сложном нелинейном мире и использовать креативные возможности синергетических эффектов»3.
Положение С раскрыто в работе одного из авторов4. В ней
показано, что деятельность по разработке даже простой миниатюрной программы носит нелинейный характер. Таким образом, речь идет не просто об изучении информатики
по
учебникам, а о работе с предметом «Информатика» путем (через, посредством) создания и анализа программных решений,
и этот вид деятельности является основным.
1
Президент Немецкого общества по изучению сложных систем и нелинейной динамики.
2
Мы бы добавили: и педагоги.
3
Майнцер К. Сложносистемное мышление. Материя, разум, человечество.
Новый синтез. М.: Книжный дом «Либроком»/URSS, 2009.
4
Окулов С. М. Информатика: развитие интеллекта школьников. 2-е изд. М.:
БИНОМ. Лаборатория знаний, 2008.

Вместо предисловия
Рассмотрим положение B. Компонентом среды является
содержание предмета, и именно часть этого содержания представлена в данной книге. Диапазон представления достаточно
обширен — от простых проблем до достаточно сложных, но
главное в том, что, несмотря на кажущуюся сложность проблем, авторы пытались показать те простые идеи, положения,
которые лежат в основе их решения. В указанной работе одного из авторов раскрывается суть сложности и открытости содержания,
а
это
необходимое
условие,
если
так
можно
выразиться, его синергетичности. Однако при всей открытости
содержания принцип его фундаментальности является основным, ибо образование, особенно школьное, не может быть
флюгером, отрабатывающим последние и быстропроходящие
новомодные веяния (особенно в информатике).
Мы не будем раскрывать основные моменты по созданию синергетической среды обучения, они известны1. Напомним только, что речь не идет о простом школьном курсе по информатике
(он, если так можно выразиться, лишь один из элементов
среды). Среда — это большее, тем более что она находится в
определенном противоречии с традиционной классно-урочной
системой изучения предмета. Эта система насквозь дуальна.
Ученик, по образному выражению К. Поппера, рассматривается «как сосуд по вливанию жидкости (знаний)». Уход от дуализма в образовании кажется утопией, но известные «площадки»
(г. Санкт-Петербург, г. Саратов, г. Новосибирск, г. Казань,
г. Мытищи Московской области, СУНЦ МГУ г. Москва), в которых созданы определенные среды (каждая имеет свое, специфическое «лицо», но построены они на единых принципах) по
развитию интеллекта школьника через изучение информатики,
вселяют надежду.
1
Окулов С. М. Информатика: развитие интеллекта школьников. 2-е изд. М.:
БИНОМ. Лаборатория знаний, 2008.

Введение
Новое по самому своему определению — это
преходящая сторона вещей… Самое лучшее в
новом то, что отвечает старому устремлению.
П. Валери
Природа нового парадоксальна: ничто не ново
в этом открытом креативном, т. е. постоянно
творящем новое, мире.
Е. Н. Князева, С. П. Курдюмов
В историческом плане понятие «динамическое программирование» было введено Ричардом Беллманом (Richard Bellman)
в 1950-х годах и определяло раздел прикладной математики под
названием «исследование операций». Круг исследуемых задач
был достаточно четко обозначен. Это методы поиска оптимальных (наилучших) решений в задачах управления системами, но
с одной, если так можно выразиться, особенностью. Как изменение самой системы во времени, так и процесс управления системой допускал разбивку по времени на этапы (шаги). Отсюда и
термин «динамическое» — изменяющееся во времени. Но так
можно представить (описать) практически любую систему
управления. Особенность динамического программирования заключалась в том, что допускалась разбивка процесса на фиксированные промежутки времени и в целом оптимальное решение
задачи как бы складывалось из оптимальных решений на каждом из промежутков (этапе, шаге). Термин «динамическое программирование»
(dynamic
programming)
в
данном
случае
никоим образом не связан с разработкой программ для компьютера, так же как, например, и «линейное программирование»
(linear programming). Он означает нечто другое, а именно строго
заданную последовательность операций (арифметических, логических) по нахождению оптимального решения. Фактически
это алгоритм решения задачи.
В ходе дальнейшего развития, но уже не раздела прикладной математики, а информатики в целом с понятием «динамическое программирование» произошла некая трансформация.
Оно очерчивает вполне определенный метод проектирования
алгоритмов, который не ограничивается только задачами
оптимизации. Естественно, этот метод не универсален, он работоспособен для вполне определенного класса задач. В идее
разбивки задачи на подзадачи и компоновки решения задачи
из решений подзадач нет ничего нового — это универсальный

Введение
метод. Смысл (суть) заложен в интерпретации терминов «разбивка» и «компоновка». Задача должна допускать разбивку на
подзадачи того же вида (типа) так, чтобы её решение как бы
складывалось, компоновалось из решений подзадач. Другими
словами, должны быть выведены (определены) функциональные зависимости (рекуррентные соотношения) между решениями подзадач. Тогда, начиная, например, с небольших задач,
мы постепенно получаем решения все больших задач и наконец доходим до решения исходной задачи. Особенность динамического программирования как метода заключается и в том,
что каждая подзадача решается только один раз. Результат её
решения запоминается и затем, при решении следующих
подзадач, используется как данное. Итак, два ключевых момента: «связь» и «запоминание».
Казалось бы, в чем сложность? Дана задача — применяй
метод, как в случае перебора с возвратом. Но, к сожалению,
а может быть к счастью, не все так просто. Универсальных рекомендаций о том, решается или нет конкретная задача с помощью динамической схемы, не разработано. Это необходимо
определить, понять, что бывает сделать в определенных случаях достаточно сложно. И так как отсутствуют строгие правила
(леммы, теоремы и так далее), это не случай теоремы Пифагора, то остается идти, познавая метод, только от практики решения конкретных задач.
Структура книги
В главе 1 рассмотрен ряд простых задач. О динамическом
программировании не говорится. Задачи служат как бы «затравкой». Идеи метода динамического программирования используются, но детального «разговора» о них нет. С одной
стороны, закладывается базис для понимания метода, а с другой, появляется материал, на который мы имеем право ссылаться в последующем изложении.
В главе 2 излагаются общие положения метода и показываются способы его реализации.
В главе 3 задачи, решаемые методом динамического программирования, классифицируются. Эта классификация идет
«от практики» работы со школьниками, она не встречается в
учебной литературе. Вероятно, что сделана первая попытка такой работы, поэтому авторы сознательно подставляют себя под
критику (но «не кусайте» слишком сильно).