Наибольшая общая подпоследовательность
Сопоставляйте две строки с таблицей DP
«Наибольшая общая подпоследовательность» — бесплатный урок Competitive Programming Academy на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Competitive Programming Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Competitive Programming Academy содержит 4 уроков всего.
Что такое подпоследовательность
Подпоследовательность сохраняет порядок символов, но может пропускать некоторые из них. Из «abcde» можно получить «ace», но никогда «aec».
Цель LCS
Для двух строк наибольшая общая подпоследовательность — это самая длинная последовательность, которая встречается в обеих строках в одном и том же относительном порядке.
Перейдите к сетке
Сравнивайте префиксы двух строк. Двумерная таблица по их длинам превращает эту задачу в знакомую задачу на сетке с DP.
Определите состояние
Пусть dp[i][j] — длина LCS для первых i символов A и первых j символов B.
Когда символы совпадают
Если A[i-1] равно B[j-1], эта общая буква увеличивает длину LCS. Прибавьте единицу к значению по диагонали dp[i-1][j-1].
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1] + 1Когда они различаются
Если буквы различаются, отбросьте один символ из любой строки и сохраните лучший результат. Возьмите максимум двух соседних значений.
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])Базовый случай
У пустого префикса нет общих символов, поэтому длина LCS равна нулю. Строка 0 и столбец 0 полностью заполнены нулями.
dp = [[0] * (m+1) for _ in range(n+1)]Одна дополнительная строка и один столбец
Размер таблицы n+1 на m+1 создаёт свободную нулевую границу. Благодаря этому на краях не нужны неудобные проверки границ.
Заполните таблицу
Перебирайте i и j, начиная с 1. Каждой ячейке нужны только значения сверху, слева и по диагонали — они уже вычислены.
for i in range(1, n+1):
for j in range(1, m+1):
...Прочитайте длину
Полная длина LCS находится в углу. Ответ — это dp[n][m] после заполнения всех ячеек.
length = dp[n][m]Сложность
Вы обращаетесь к каждой ячейке один раз, поэтому затраты составляют O(n умножить на m) по времени и памяти. Этого с запасом хватает для строк длиной до нескольких тысяч символов.
Быстрая проверка
Текущие символы A[i-1] и B[j-1] совпадают. Какое обновление верно?
Повторение: LCS
Постройте таблицу размера n+1 на m+1: при совпадении прибавьте единицу к значению по диагонали, иначе возьмите максимум соседних значений. В углу находится длина. 🔗
Часто задаваемые вопросы
Урок «Наибольшая общая подпоследовательность» бесплатный?
Да — полный текст урока «Наибольшая общая подпоследовательность» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Competitive Programming Academy, подпишись на CoddyKit PRO. Курс Competitive Programming Academy содержит 4 уроков всего.
Чему я научусь в уроке «Наибольшая общая подпоследовательность»?
Сопоставляйте две строки с таблицей DP Ты практикуешь Competitive Programming Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Competitive Programming Academy?
Предыдущий опыт не требуется. Competitive Programming Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.
Сколько времени занимает урок «Наибольшая общая подпоследовательность»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Competitive Programming Academy?
Да. Каждый урок Competitive Programming Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Подсчёт путей по сетке
- Минимальная сумма пути с препятствиями
- Наибольшая общая подпоследовательность
- Расстояние редактирования шаг за шагом