16
правок
Изменения
Нет описания правки
{{Задача
|definition=
}}
d = tmp
''<font color="green">// ответ — lcs[n]</font>''
== Длинна кратчайшей общей подпоследовательности ==
Для двух подпоследовательностей <tex> X = \left \langle x_1, x_2, ..., x_m \right \rangle </tex> и <tex> Y = \left \langle y_1, y_2, ..., y_n \right \rangle </tex> длинна кратчайшая общей подпоследовательности равна
<tex>
|SCS(X,Y)| = n + m - |LCS(X,Y)|
</tex>
== См. также ==
*[[Задача о наибольшей возрастающей подпоследовательности]]
*[[Наибольшая общая возрастающая подпоследовательность]]
*[[Задача о наибольшей общей палиндромной подпоследовательности]]
== Список литературы ==
