длинный общий подпоследовательности с использованием линейной памяти

Question

Я пытаюсь найти алгоритм, который использует линейное пространство памяти для:

Предоставлено двух строк х и у над произвольным алфавитом, определить их самую длинную общую последовательность суб.

Answer 1

Обратите внимание, что когда вы вычисляете следующую строку таблицы в решении динамического программирования для решения проблемы LCS, вам нужна только предыдущая строка и текущая строка. Затем вы можете изменить решение динамического программирования, чтобы отслеживать только предыдущую строку и текущую строку вместо таблицы m x n. Каждый раз, когда вы достигаете конца текущей строки, вы устанавливаете предыдущую строку в текущую строку и начинаете с начала строки снова. Вы делаете это m раз, где m - количество строк в таблице. Это будет использовать пространство, линейное по числу столбцов.