DP по двум последовательностям

Когда сравниваются две строки или два массива, одного индекса недостаточно: нужно знать, сколько символов рассмотрено в каждой последовательности. Базовый пример — длина наибольшей общей подпоследовательности (LCS).

Как сравнить два префикса строк

Для строк text1 и text2 найти максимальную длину последовательности символов, которая встречается в обеих строках в том же порядке, но не обязательно подряд. У "abcde" и "ace" LCS равна "ace", длина 3.

Что перебирают все подпоследовательности

Можно перечислить все подпоследовательности первой строки (2^n) и проверять, является ли каждая подпоследовательностью второй. Или рекурсивно при несовпадении удалить символ из первой либо второй строки. В обоих вариантах одинаковые пары суффиксов появляются многократно.

Где пары префиксов возникают повторно

Рекурсия повторно решает задачу для одинаковых префиксов. Нам не нужна конкретная выбранная подпоследовательность, чтобы узнать её длину; достаточно пары длин префиксов.

Как совпадение и пропуск заполняют LCS

dp[i][j] — длина LCS первых i символов text1 и первых j символов text2. Если последние символы равны, они могут завершать общую подпоследовательность: dp[i][j] = dp[i-1][j-1] + 1. Иначе общий оптимум не может использовать оба последних символа одновременно, поэтому один из них пропускается: max(dp[i-1][j], dp[i][j-1]).

Отдельный переход для расстояния редактирования

Независимая задача Edit Distance не является «LCS с другим ответом». Пусть edit[i][j] — минимальное число операций, превращающих первые i символов первой строки в первые j символов второй. Базы: edit[i][0] = i (удалить все символы) и edit[0][j] = j (вставить все символы).

Если последние символы равны, edit[i][j] = edit[i-1][j-1]: за совпадение платить не нужно. Иначе выбирается ровно одна последняя операция:

• удалить последний символ первой строки: edit[i-1][j] + 1;
• вставить последний символ второй строки: edit[i][j-1] + 1;
• заменить последний символ первой строки: edit[i-1][j-1] + 1.

Значит, при несовпадении берём минимум этих трёх величин, а не максимум верхней и левой ячеек, как в LCS.

Разобранный пример: horse → ros

Для префиксов строк horse и ros таблица заканчивается значением edit[5][3] = 3. В частности, edit[2][2] = 1: заменить h на r, а o уже совпадает. В правом нижнем углу последний символ e не совпадает с s, поэтому edit[5][3] = 1 + min(edit[4][3], edit[5][2], edit[4][2]) = 1 + min(2, 4, 3) = 3.

Один конкретный путь: horse → rorse → rose → ros — замена h на r, затем два удаления. Таблица хранит число операций, а не обязана выбирать именно этот путь: несколько путей могут иметь одинаковую минимальную длину.

Что хранит ячейка двухстрочной таблицы

После обработки ячейки dp[i][j] она содержит точную длину LCS двух указанных префиксов. При заполнении по строкам уже готовы диагональ, верхняя и левая ячейки, от которых зависит переход.

Как пройти таблицу префиксов

1. Создать таблицу (n+1) x (m+1) из нулей: пустой префикс имеет LCS длины 0 с любым префиксом.
2. Для i = 1..n и j = 1..m сравнить text1[i-1] и text2[j-1].
3. При равенстве взять диагональ плюс 1; иначе максимум сверху и слева.
4. Вернуть правую нижнюю ячейку.

Как кодировать LCS без восстановления пути

Код считает длину. Чтобы восстановить саму подпоследовательность, пройдите из правого нижнего угла назад: при совпадении идите по диагонали, иначе к соседу с большим значением.

C++17

#include <algorithm>
#include <cassert>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int lcsLength(const string& first, const string& second) {
    vector<vector<int>> dp(first.size() + 1, vector<int>(second.size() + 1, 0));

    for (size_t i = 1; i <= first.size(); ++i) {
        for (size_t j = 1; j <= second.size(); ++j) {
            if (first[i - 1] == second[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[first.size()][second.size()];
}

int main() {
    assert(lcsLength("abcde", "ace") == 3);
    assert(lcsLength("abc", "def") == 0);
    cout << lcsLength("stone", "longest") << '\n';
}

Python 3

def lcs_length(first: str, second: str) -> int:
    dp = [[0] * (len(second) + 1) for _ in range(len(first) + 1)]

    for i in range(1, len(first) + 1):
        for j in range(1, len(second) + 1):
            if first[i - 1] == second[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[-1][-1]


assert lcs_length("abcde", "ace") == 3
assert lcs_length("abc", "def") == 0
print(lcs_length("stone", "longest"))

Во что обходится сравнение двух строк

Время O(nm), память O(nm). Для длины память можно сжать до одной строки O(min(n,m)), но для восстановления пути обычно нужна вся таблица или дополнительная стратегия. Алгоритм сравнивает символы буквально: регистр, пробелы и Unicode-нормализация должны быть определены условиями отдельно.

Где подпоследовательность не является подстрокой

Пустая строка даёт 0. Повторяющиеся символы не означают, что можно брать их без сохранения порядка. LCS — не подстрока: в "abcde" и "ace" ответ 3, хотя ace не идёт подряд. Восстановление при равных верхней и левой ячейках может дать разные, но одинаково длинные ответы.

Какими парами строк проверить DP

• "", "abc" -> 0;
• "abcde", "ace" -> 3;
• "abc", "def" -> 0;
• одинаковые строки;
• повторения: "aab", "azab" -> 3;
• случай, где общая подпоследовательность не является подстрокой.

Когда два индекса образуют состояние

Сигналы: две строки/последовательности, сохранение относительного порядка, «совпадают или пропускаем символ», «минимум правок», «длиннейшая общая часть». Если решение после сравнения двух текущих элементов переходит к двум индексам, это кандидат на dp[i][j].

Когда LCS не отвечает на нужный вопрос

Не используйте LCS для требования непрерывного фрагмента — там другой переход для longest common substring. Для очень длинных строк O(nm) может быть неприемлем; нужны ограничения, битсет-оптимизация или иной алгоритм. Не смешивайте LCS и edit distance: у них разные переходы и цель.

Самопроверка несовпадающих последних букв

Вопрос: почему при несовпадении берут max(top, left), а не диагональ?
Ответ: диагональ удалит сразу оба последних символа. Оптимальная подпоследовательность может сохранить один из них, поэтому надо попробовать пропустить только первый или только второй.

Самопроверка порядка символов

Вопрос: чему равна LCS "ab" и "ba"?
Ответ: 1. Можно выбрать a или b, но нельзя выбрать два символа в одном и том же порядке в обеих строках.

Потренируйте обратный проход по LCS

Восстановите одну LCS для "AGGTAB" и "GXTXAYB". Начните из dp[n][m], при совпадении добавляйте символ и идите по диагонали, иначе идите к большему соседу. Запишите, где появляется неоднозначность.

Самостоятельная задача о правках строк

Решите без подсказок. До кода назовите смысл ячейки, три допустимые операции и базы пустого префикса.

Задача 1

Реализуйте расстояние редактирования для двух строк: минимальное число вставок, удалений и замен, превращающих первую строку во вторую. Это независимая попытка для задачи LeetCode Edit Distance.

Что объединяет задачи о двух префиксах

В двухпоследовательностном DP пара индексов — это не роскошь, а минимальное описание двух префиксов. Формула следует из того, можно ли взять оба последних элемента одновременно.