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


Что: Семинар
Когда: Суббота, 29 сентября 2018, 16:20–17:55
Где: НГУ, ауд. 2128

Описание

Расстояние редактирования. Разрешаем редактировать обе строки. Добавления не нужны. Динамика: R[i, j] - расстояние между i-префиксом и j-префиксом. Смотрим на последние символы, разбираем случаи. Рекуррентная формула.

Задача о рюкзаке (Knapsack). Множество состояний и рекуррентная формула. Обратный ход (кратко).

Задача о порядке перемножения матриц. Множество состояний и рекуррентная формула. Обратный ход (кратко).

Видео