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

Вместо предисловия 5
Введение 9

Глава 1. Простые задачи

1.1. Числа Фибоначчи 13
1.2. Биномиальные коэффициенты, или Нахождение числа сочетаний 17
1.3. Наибольший квадрат 20
1.4. Задача о Черепашке 26

Глава 2. Основной принцип и метод реализации на основе рекуррентных соотношений

2.1. Вводные замечания 33
2.2. Множество решаемых задач, вычисляемая функция и рекуррентные соотношения 35
2.3. Граф зависимостей задач 38
2.4. Общая схема 42
2.5. Пример решения задачи 45

Глава 3. Типы задач по динамическому программированию

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