| Введение | 8
|
| Глава 1. Рекуррентные соотношения | 9
|
| 1.1.Ханойская башня | 9
|
| 1.2.Как решать задачи с рекуррентностями | 13
|
| 1.3.Задача о разрезании пиццы | 13
|
| 1.4.Задача Иосифа Флавия | 16
|
| 1.5.Лягушка и шестиугольник | 18
|
| 1.6.Заключение | 24
|
| 1.7.Что еще почитать | 24
|
| 1.8.Задачи | 25
|
| 1.9.Ответы на задачи | 26
|
| Глава 2. Вычисление рекуррентностей на компьютере | 29
|
| 2.1.Числа Фибоначчи | 29
|
| 2.1.1. Рекурсивный алгоритм для вычисления чисел Фибоначчи | 30
|
| 2.1.2. Вычисление чисел Фибоначчи с помощью последовательного заполнения массива | 32
|
| 2.2.Домино | 33
|
| 2.2.1. Покрытие прямоугольника 2 ? n | 33
|
| 2.2.2. Покрытие прямоугольника 3 ? n | 39
|
| 2.3.Вычисление рекуррентностей | 45
|
| 2.4.Что еще почитать | 46
|
| 2.5.Задачи | 46
|
| 2.6.Ответы на задачи | 47
|
| 2.7.Упражнения | 48
|
| Глава 3. Динамическое программирование | 49
|
| Глава 4. Динамическое программирование и одно целое число | 53
|
| 4.1.Размен | 53
|
| 4.2.Ход конем | 58
|
| 4.3.Количество способов решения задачи | 61
|
| 4.4.Задачи | 62
|
| 4.5.Решения | 63
|
| 4.6.Упражнения | 65
|
| Глава 5. Динамическое программирование и два целых числа | 67
|
| 5.1.Биномиальные коэффициенты | 67
|
| 5.2.Задача о лесенках | 71
|
| 5.3.Путь в матрице | 75
|
| 5.4.Заключение | 77
|
| 5.5.Упражнения | 77
|
| Глава 6. Динамическое программирование и одномерные массивы | 79
|
| 6.1.Наилучшее решение задачи (задача о кузнечике со стоимостями) | 79
|
| 6.2.Сообщение | 83
|
| 6.3.Наибольшая возрастающая подпоследовательность | 84
|
| 6.4.Наилучшее расписание | 86
|
| 6.5.Заключение | 90
|
| 6.6.Упражнения | 90
|
| Глава 7. Динамическое программирование и последовательности | 93
|
| 7.1.Палиндром | 93
|
| 7.2.Самый длинный палиндром | 97
|
| 7.3.Количество палиндромов | 100
|
| 7.4.Наибольшая общая подпоследовательность | 101
|
| 7.5.Заключение | 103
|
| 7.6.Упражнения | 103
|
| Глава 8. Динамическое программирование и подмножества | 105
|
| 8.1.Размен 2 | 105
|
| 8.2.Задача о рюкзаке | 109
|
| 8.3.Задача линейного разбиения | 112
|
| 8.4.Заключение | 116
|
| 8.5.Упражнения | 117
|
| 8.5.1. Суммы | 117
|
| 8.5.2. Копилка | 117
|
| Глава 9. Динамическое программирование и матрицы | 119
|
| 9.1.Путь в матрице 2 | 119
|
| 9.2.Маршруты | 121
|
| 9.3.Упражнения | 124
|
| Глава 10. Динамическое программирование по профилю | 125
|
| 10.1. Снова домино | 125
|
| 10.2. Задача о симпатичных узорах | 132
|
| 10.3. Изломанные профили | 137
|
| 10.4. Заключение | 138
|
| Глава 11. Динамическое программирование и игры с полной информацией | 139
|
| 11.1. Игра Баше | 139
|
| 11.2. Игра умножения | 145
|
| 11.3. Игра «Ферзя в угол» | 150
|
| 11.4. Крестики-нолики | 153
|
| 11.5. Обобщенный алгоритм для анализа антагонистических игр с полной информацией | 159
|
| 11.6. Что еще почитать | 161
|
| Глава 12. Динамическое программирование и все-все-все | 163
|
| 12.1. Поиск кратчайшего пути | 163
|
| 12.2. Мемоизация | 164
|
| 12.3. Игры с полной информацией посложнее | 165
|
| Приложение. Исходные тексты решений задач | 167
|
| Глава 2. Вычисление рекуррентностей на компьютере | 167
|
| 2.2.Домино | 167
|
| Глава 4. Динамическое программирование и одно целое число | 168
|
| 4.1.Размен | 168
|
| 4.2.Ход конем | 169
|
| Глава 5. Динамическое программирование и два целых числа | 170
|
| 5.1.Биномиальные коэффициенты | 170
|
| 5.2.Задача о лесенках | 170
|
| 5.3.Путь в матрице | 171
|
| Глава 6. Динамическое программирование и одномерные массивы | 172
|
| 6.1.Кузнечик | 172
|
| 6.2.Сообщение | 173
|
| 6.3.Наибольшая возрастающая подпоследовательность | 173
|
| 6.4.Наилучшее расписание | 174
|
| Глава 7. Динамическое программирование и последовательности | 176
|
| 7.1.Палиндром | 176
|
| 7.2.Самый длинный палиндром | 177
|
| 7.3.Количество палиндромов | 179
|
| 7.4.Наибольшая общая подпоследовательность | 180
|
| Глава 8. Динамическое программирование и подмножества | 180
|
| 8.1.Размен 2 | 180
|
| 8.2.Задача о рюкзаке | 182
|
| 8.3.Задача линейного разбиения | 182
|
| Глава 9. Динамическое программирование и матрицы | 184
|
| 9.1.Путь в матрице 2 | 184
|
| 9.2.Маршруты | 185
|
| Глава 10. Динамическое программирование по профилю | 187
|
| 10.1. Снова домино | 187
|
| 10.2. Задача о симпатичных узорах | 188
|
| Глава 11. Динамическое программирование и игры с полной информацией | 189
|
| 11.1. Игра Баше | 189
|
| 11.2. Игра умножения | 190
|
| 11.3. Игра «Ферзя в угол» | 191
|
| 11.4. Крестики-нолики | 192
|
| Литература | 196
|
Тем, кто хоть раз участвовал в олимпиадах по программированию, наверняка попадались задачи, которые можно попытаться решить полным перебором вариантов ответов. При этом полный балл такое решение не получает, оставляя начинающих программистов в замешательстве. Ведь на их-то компьютере все работало.
Правильное решение для тех самых начинающих часто кажется каким-то волшебством. И непонятно, как, зная такое решение, научиться придумывать такое же волшебство самому, даже если знать, что использовалась техника, называемая «динамическим программированием».
Это самое «динамическое программирование» помогает организовать перебор ответов так, чтобы он укладывался в отведенное время. Или же решение строится совсем иначе, и перебор становится не нужен.
Динамическое программирование используется не только в искусственных олимпиадных задачах, с которыми в реальной жизни большинство программистов и не сталкивается. Сам принцип встречается довольно часто: и в разработке игр и ботов для них (например, при поиске кратчайшего пути), и в компиляторах (некоторые действительно их пишут), и в веб-программировании (в совсем уж широком смысле).
Эта книга отличается от других, посвященных динамическому программированию, тем, что мы попробуем разобраться с ним, отталкиваясь от математических идей, лежащих в основе. Алгебре учат всех, а вот рекурсии — уже нет. Также мы рассмотрим, как можно улучшить уже существующие программы, использующие полный перебор (все-таки акцент у нас будет на олимпиадные задачи, ведь не каждому захочется писать собственный компилятор).
Довгалюк Павел Михайлович