Неделя 11

Лекция 11. Динамическое программирование на строках: наибольшая общая подпоследовательность (LCS) с восстановлением, наибольшая возрастающая подпоследовательность (LIS) за $O(n^2)$ и схема $O(n\log n)$, расстояние Левенштейна и восстановление выравнивания правок.

Семинар 11. Практика по задаче о рюкзаке 0/1 (материал лекции 10): таблица $dp[i][w]$, обратный ход для восстановления набора предметов, оптимизация памяти до одного массива, контрпример неограниченного варианта.