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

План лекции

Вспоминаем, что такое динамика. Когда нужна, а когда не нужна динамика.
Основные применения динамики:

1. Подсчет количества объектов. Пример: числа Каталана.
2. Нахождение минимального (максимального) решения. Пример: задача «Банкомат».
3. Позиционные игры. Пример: задача «Ферзя в угол» или «Игра с датами».

Задача «Ход конем».
Задача «восстановление скобок».
Задача рюкзака и частный случай выбора камней заданной массы.
Задача умножения матриц.
Задача оптимальной триангуляции многоугольника.
Задача нахождения наибольшей общей подпоследовательности.
Задача «Два шаблона».

Что еще хочется (чего я пока не знаю)? Динамику на нелинейном множестве (например, динамику на графе, но интересную и нетривиальную) и динамику по >2 параметрам.

Список задач, которые можно рассмотреть

1. Умножение матриц. // Кормен, Шень.
2. Набольшая общая подпоследовательность. // Кормен
3. Оптимальная триангуляция многоугольника. // Кормен, Шень.
4. Битоническая задача коммивояжера. // Кормен
5. Минимальная стоимость проезда по ж/д в одну сторону // Шень
6. Рюкзак
7. Рюкзак с множеством предметов одного вида // Окулов
8. Восстановление скобок // Особенности...
9. Ход конем // Особенности...
10. Два шаблона (min строка, удовлетворяющая обоим шаблонам) // Особенности...
11. Жадный калькулятор (расставить скобки так, чтобы значение было максимальным) // Особенности...
12. Банкомат (набрать заданную сумму минимальным числом монет)
13. Максимальная интервальная сумма.

Литература

1. А. Шень. Программирование: теоремы и задачи.
2. Т.Кормен, Ч.Лейзерсон, Р.Ривест. Алгоритмы: построение и анализ.
3. В.Беров, А.Лапунов, В.Матюхин, А.Пономарев. Особенности национальных задач по информатике.
4. С.Скиена, М.Ревилла. Олимпиадные задачи по программированию. Руководство по подготовке к соревнованиям.
5. С.Окулов. Программирование в алгоритмах.
6. Ф.Меньшиков. Олимпиадные задачи по программированию.