12
правок
Изменения
м
Нет описания правки
''<font color="green">// подсчёт таблиц</font>''
'''int''' LCS(x: '''intvector''', y: '''intvector'''):
m = length(x)
n = length(y)
Заметим, что для вычисления <tex> lcs[i][j] </tex> нужны только <tex> i </tex>-ая и <tex> (i-1) </tex>-ая строчки матрицы <tex> lcs </tex>. Тогда можно использовать лишь <tex> 2 \cdot min(m, n) </tex> элементов таблицы:
'''int''' LCS2(x: '''intvector''', y: '''intvector'''):
'''if''' length(x) < length(y) ''<font color="green">// в таблице будет length(y) столбцов, и если length(x) меньше, выгоднее поменять местами x и y</font>''
swap(x, y)
Также можно заметить, что от <tex> (i - 1) </tex>-ой строчки нужны только элементы с <tex> (j - 1) </tex>-го столбца. В этом случае можно использовать лишь <tex> min(m, n) </tex> элементов таблицы:
'''int''' LCS3(x: '''intvector''', y: '''intvector'''):
'''if''' length(x) < length(y) ''<font color="green">// в таблице будет length(y) столбцов, и если length(x) меньше, выгоднее поменять местами x и y</font>''
swap(x, y)
