Разбор задачи Сравнение геномов (редакционное расстояние)

Идея задачи

Даны две строки s и t, состоящие из символов A, C, G, T. Нужно найти минимальное количество операций, необходимых, чтобы превратить строку s в строку t.

Разрешены три операции:

1. Вставка одного символа.
2. Удаление одного символа.
3. Замена одного символа на другой.

Это классическая задача на редакционное расстояние (distance of Levenshtein).

Почему здесь подходит динамическое программирование

Если мы хотим сравнить две строки целиком, удобно сначала научиться отвечать на вопрос для их префиксов.

Пусть:

dp[i][j] — минимальное количество операций, чтобы преобразовать первые i символов строки s в первые j символов строки t.

Тогда ответом будет dp[n][m], где:

• n = len(s)
• m = len(t)

Такой подход естественен: ответ для больших префиксов строится через ответы для меньших.

Базовые случаи

1. Преобразовать пустую строку в префикс длины j

Если строка s пустая, а у строки t есть j символов, то нужно просто вставить эти j символов:

dp[0][j] = j

2. Преобразовать префикс длины i в пустую строку

Если строка t пустая, то нужно удалить все i символов:

dp[i][0] = i

Переход динамики

Рассмотрим состояние dp[i][j].

Мы хотим преобразовать s[:i] в t[:j].

Смотрим на последние символы этих префиксов:

• s[i-1]
• t[j-1]

Случай 1. Символы равны

Если s[i-1] == t[j-1], то последний символ уже совпадает, ничего делать не нужно:

dp[i][j] = dp[i-1][j-1]

Случай 2. Символы не равны

Тогда есть три варианта:

1. Удалить последний символ из s

Преобразуем s[:i-1] в t[:j], а потом удаляем s[i-1]:

dp[i][j] = dp[i-1][j] + 1

2. Вставить символ в s

Преобразуем s[:i] в t[:j-1], а затем вставляем символ t[j-1]:

dp[i][j] = dp[i][j-1] + 1

3. Заменить последний символ

Преобразуем s[:i-1] в t[:j-1], затем заменяем s[i-1] на t[j-1]:

dp[i][j] = dp[i-1][j-1] + 1

Итоговый переход:

if s[i-1] == t[j-1]:
    dp[i][j] = dp[i-1][j-1]
else:
    dp[i][j] = min(
        dp[i-1][j] + 1,
        dp[i][j-1] + 1,
        dp[i-1][j-1] + 1
    )

Удобно объединить оба случая через стоимость:

• cost = 0, если символы равны
• cost = 1, если символы различны

Тогда:

dp[i][j] = min(
    dp[i-1][j] + 1,
    dp[i][j-1] + 1,
    dp[i-1][j-1] + cost
)

Небольшой пример

Пусть:

• s = ACGT
• t = ACGG

Первые три символа совпадают. Отличается только последний:

• T -> G

Достаточно одной замены, значит ответ равен 1.

Почему можно хранить не всю таблицу

Если посмотреть на переходы, то для вычисления текущей строки dp нужны только:

• предыдущая строка,
• текущая строка.

Значит, вместо таблицы n × m можно хранить только два массива длины m + 1:

• prev — предыдущая строка,
• cur — текущая строка.

Это уменьшает расход памяти с O(nm) до O(m).

Так как в решении выгодно делать второй строкой более короткую, можно дополнительно оптимизировать память до O(min(n, m)).

Пошаговая логика оптимизированного решения

1. Считываем строки s и t.
2. Если t длиннее s, меняем их местами, чтобы массивы были короче.
3. Создаём массив prev, где изначально prev[j] = j.
4. Перебираем i от 1 до n.
5. Для каждой позиции j от 1 до m считаем текущий ответ по формуле перехода.
6. После обработки строки меняем prev и cur местами.
7. Ответ находится в prev[m].

Корректность решения

Докажем, что описанный алгоритм действительно находит минимальное число операций.

Что хранит DP

dp[i][j] — минимальное количество операций для преобразования s[:i] в t[:j].

База

• dp[0][j] = j, потому что нужно j вставок.
• dp[i][0] = i, потому что нужно i удалений.

Это очевидно минимально.

Переход

Для dp[i][j] рассматриваем последнюю операцию в оптимальном преобразовании.

Она может быть только одной из трёх:

1. Удаление последнего символа s[i-1], тогда до этого мы уже оптимально преобразовали s[:i-1] в t[:j].
2. Вставка символа t[j-1], тогда до этого мы уже оптимально преобразовали s[:i] в t[:j-1].
3. Совпадение или замена последнего символа, тогда до этого мы оптимально преобразовали s[:i-1] в t[:j-1].

Других вариантов последней операции не существует. Значит, минимум по этим трём случаям и есть оптимальный ответ.

Следовательно, все значения DP вычисляются корректно, а значит корректен и итоговый ответ dp[n][m].

Асимптотика

Пусть:

• n = |s|
• m = |t|

Тогда:

• Время: O(n * m)
• Память: O(min(n, m))

При ограничениях до 2000 такой алгоритм проходит уверенно.

Типичные ошибки

1. Неправильная индексация

Очень важно не путать:

• символ s[i-1]
• состояние dp[i][j]

DP обычно идёт по длинам префиксов, а индексы в строках — с нуля.

2. Забыть про базу

Если не заполнить dp[0][j] и dp[i][0], переходы будут работать неверно.

3. Перепутать смысл вставки и удаления

Это частая ошибка. Но если держать в голове смысл состояния dp[i][j], всё становится понятно:

• dp[i-1][j] + 1 — удалили символ из s
• dp[i][j-1] + 1 — вставили символ в s

4. Использовать полную таблицу без необходимости

Полная таблица тоже корректна, но оптимизация до двух строк делает решение аккуратнее.

Решение на C++

#include <bits/stdc++.h>
using namespace std;

int main() {

    string s, t;
    if (!(cin >> s)) return 0;
    cin >> t;

    // Для экономии памяти будем хранить DP по более короткой строке
    if (s.size() < t.size()) swap(s, t);

    int n = (int)s.size();
    int m = (int)t.size();

    vector<int> prev(m + 1), cur(m + 1);

    // База: расстояние от пустой строки до префиксов t
    for (int j = 0; j <= m; ++j) {
        prev[j] = j;
    }

    for (int i = 1; i <= n; ++i) {
        cur[0] = i;
        for (int j = 1; j <= m; ++j) {
            int cost = (s[i - 1] == t[j - 1]) ? 0 : 1;
            cur[j] = min({
                prev[j] + 1,        // удаление
                cur[j - 1] + 1,     // вставка
                prev[j - 1] + cost  // замена или совпадение
            });
        }
        prev.swap(cur);
    }

    cout << prev[m] << '\n';
    return 0;
}

Решение на Python

import sys


def main():
    s = sys.stdin.readline().strip()
    t = sys.stdin.readline().strip()

    # Для экономии памяти делаем вторую строку более короткой
    if len(s) < len(t):
        s, t = t, s

    n, m = len(s), len(t)

    prev = list(range(m + 1))
    cur = [0] * (m + 1)

    for i in range(1, n + 1):
        cur[0] = i
        for j in range(1, m + 1):
            cost = 0 if s[i - 1] == t[j - 1] else 1
            cur[j] = min(
                prev[j] + 1,        # удаление
                cur[j - 1] + 1,     # вставка
                prev[j - 1] + cost  # замена или совпадение
            )
        prev, cur = cur, prev

    print(prev[m])


if __name__ == "__main__":
    main()

Вывод

Это классическая задача на динамическое программирование по двум строкам.

Ключевая идея состоит в том, чтобы рассматривать минимальную стоимость преобразования префиксов и понимать, какой могла быть последняя операция. После этого переход получается почти автоматически.

Главная ценность этой задачи — она учит:

• правильно формулировать состояние DP;
• аккуратно строить переходы по смыслу операций;
• оптимизировать память без потери корректности.

Если хорошо понять этот разбор, будет намного проще решать и другие задачи на сравнение строк и динамику по последовательностям.