Семинар 3. Динамическое программирование
Суббота, 28 сентября 2019
НГУ, ауд. 2128, НГУ, новый корпус
Расстояние редактирования. Разрешаем редактировать обе строки. Добавления не нужны. Динамика: R[i, j] - расстояние между i-префиксом и j-префиксом. Смотрим на последние символы, разбираем случаи. Рекуррентная формула.
Задача о рюкзаке (Knapsack). Множество состояний и рекуррентная формула. Обратный ход (кратко).
Задача о порядке перемножения матриц. Множество состояний и рекуррентная формула. Обратный ход (кратко).
Видео для студентов заочного отделения: https://my.compscicenter.ru/courses/algorithms-1/nsk/2018-autumn/classes/4201/