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