Код Senior Динамическое программирование обновлено
Наибольшая общая подпоследовательность
Условие
Длина наибольшей общей подпоследовательности двух строк (символы не обязаны идти подряд).
Примеры
lcs("abcde", "ace") // 3
lcs("abc", "def") // 0
lcs("", "") // 0
Как подойти
Каноническая двумерная динамика, O(n·m). Нулевая строка и столбец избавляют от проверок границ. Свёртка до двух строк даёт O(min(n,m)) памяти - назови как улучшение. Подпоследовательность (не подряд) против подстроки (подряд) - разные задачи с разными рекуррентами.
Подсказки: 2
- Таблица (длина a + 1) на (длина b + 1), нулевая строка и столбец - база.
- Совпали символы - плюс один к диагонали; нет - максимум из соседей.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.