Условие
Даны две последовательности
x[
1]...
x[
n]
и
y[
1]...
y[
k] целых чисел. Найти максимальную
длину последовательности, являющейся подпоследовательностью
обеих последовательностей. Количество операций порядка
n . k.
Решение
(Cообщено М. Н.Вайнцвайгом, А.М.Диментманом).
Обозначим через
f(
p,
q) максимальную длину
общей подпоследовательности последовательностей
x[
1]...
x[
p] и
y[
1]...
y[
q]. Тогда
x[p] y[q] |
 |
f(p,q) = max (f(p,q - 1),f(p - 1,q)); |
|
| x[p] = y[q] |
|
f(p,q) = max (f(p,q - 1),f(p - 1,q),f(p - 1,q - 1) + 1); |
|
Поскольку
f(
p -
1,
q -
1) +
1≥f(
p,
q -
1),
f(
p -
1,
q), во
втором случае максимум трёх чисел можно заменить на третье
из них.) Поэтому можно заполнять таблицу значений
функции
f, имеющую размер
n . k. Можно
обойтись и памятью порядка
k (или
n), если
индуктивно (по
p) вычислять
<
f(
p,0), ...,
f(
p,k)> (как функция
от
p этот набор индуктивен).
Источники и прецеденты использования
|
|
|
книга |
|
Автор |
А.Шень |
|
Название |
Программирование: теоремы и задачи |
|
Издательство |
МЦНМО |
|
Издание |
второе |
|
Год издания |
2004 |
|
глава |
|
Номер |
1 |
|
Название |
Переменные, выражения, присваивания |
|
параграф |
|
Номер |
3 |
|
Название |
Индуктивные функции (по А.Г.Кушниренко) |
|
задача |
|
Номер |
1.3.3 |
