Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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.Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 464 Содержание
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Содержание 5
Глава 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Содержание 7
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