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

План лекции

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

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

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

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