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

Расстояние редактирования. Разрешаем редактировать обе строки. Добавления не нужны. Динамика: R[i, j] - расстояние между i-префиксом и j-префиксом. Смотрим на последние символы, разбираем случаи. Рекуррентная формула. Задача о рюкзаке (Knapsack). Множество состояний и рекуррентная формула. Обратный ход (кратко). Задача о порядке перемножения матриц. Множество состояний и рекуррентная формула. Обратный ход (кратко). Семинар №3 в курсе “Алгоритмы и структуры данных, часть 1“, осень 2018 (Новосибирск) Преподаватели курса: Александр Александрович Стененко, Степан Юрьевич Гатилов Страница семинара на сайте CS центра: Все видео курса по порядку: