Семинар 4. Динамическое программирование (Алгоритмы и структуры данных, часть 1)

Динамическое программирование вперёд. Граф зависимостей. Процесс построения/перебора решения. Как получить по процессу решение динамическим программированием: шаги, остановка, важная информация. Параметры динамики, внесение параметра в целевую функцию. Уменьшение затрачиваемой памяти для динамики по слоям. Примеры построения динамики для наибольшей возрастающей подпоследовательности. Примеры построения динамики для задачи о рюкзаке. Решение задачи 8. Букет (http://opencup.ru/files/ocg/gp3/problems.pdf). Параметры динамики, если перебирать предметы. Параметры, если добавить сортировку. Решение за O(N S) времени и O(S) памяти. Семинар №4 в курсе "Алгоритмы и структуры данных, часть 1", осень 2018 (Новосибирск) Преподаватели курса: Александр Александрович Стененко, Степан Юрьевич Гатилов Страница лекции на сайте CS центра: https://compscicenter.ru/courses/algorithms-1/nsk/2018-autumn/classes/4213/ Все видео курса по порядку: https://www.youtube.com/playlist?list=PLlb7e2G7aSpSvqoUtSFrhZ-wAyfrQ9lMd