#algorithm
#алгоритм
Вопрос:
Мы все знаем, что алгоритм LCS (самой длинной общей подпоследовательности) для 2 строк может быть вычислен с использованием динамического программирования для 2 строк длиной m и n в O (mn) времени и пространстве.
Теперь, если мы рассмотрим k строк длиной, скажем, n1, n2, ….nk. Как мы можем распространить этот алгоритм на общий случай?
Насколько я понимаю решение DP, нам потребуется пространство O (n1 * n2 … * nk) (массив k-dim)
Есть ли способ повысить эффективность использования пространства для общего случая?
Комментарии:
1. Удачи с платным доступом, но в этой статье это обсуждается.