DP над подпоследовательностями (LIS / LCS / расстояние редактирования)

DP над подпоследовательностями (LIS / LCS / расстояние редактирования): как это работает?

Постройте таблицу с одной строкой на элемент первой последовательности. Столбцы берутся из второй.

Ячейка i и j это ответ для этих двух префиксов. Всё, что дальше них, не важно.

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

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

Нулевая строка и нулевой столбец означают пустые префиксы. В них лежат базовые значения.

Каждая строка читает только строку над собой. Значит хватает памяти на одну строку.

1. нулевая строка и столбец это нулиСравниваем AB и AC. У пустого префикса общего нет.
2. A против A: совпалоНа диагонали был 0, значит в ячейке становится 1.
3. A против C: не совпалоБерём лучшего соседа, а это 1.
4. B против C: не совпалоНи одна сторона не помогает, ячейка остаётся 1.
5. ответ = 1Единственная общая буква это A.

function longestIncreasingSubsequence(arr) {
    const dp = new Array(arr.length).fill(1);
    let best = arr.length ? 1 : 0;
    for (let i = 1; i < arr.length; i++) {
        for (let j = 0; j < i; j++) {
            if (arr[j] < arr[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
        }
        best = Math.max(best, dp[i]);
    }
    return best;
}

DP над подпоследовательностями (LIS / LCS / расстояние редактирования): разбор примера

Расстояние редактирования между словами

Верните наименьшее число посимвольных правок, превращающих одно слово в другое.

Правка вставляет, удаляет или заменяет ровно один символ.

Ячейка i и j это стоимость превращения первых i букв в первые j.

При совпадении стоимость берётся с диагонали. При расхождении это единица плюс дешёвый сосед.

function minDistance(a, b) {
    // row 0 and column 0 hold the cost of deleting a whole prefix
    const dp = Array.from({ length: a.length + 1 }, (_, i) =>
        Array.from({ length: b.length + 1 }, (_, j) => (i === 0 ? j : j === 0 ? i : 0))
    );

    for (let i = 1; i <= a.length; i++) {
        for (let j = 1; j <= b.length; j++) {
            if (a[i - 1] === b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1]; // no edit needed
            } else {
                // replace, delete, insert
                dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[a.length][b.length];
}

DP над подпоследовательностями (LIS / LCS / расстояние редактирования): когда применять?

Эти формулировки в условии ведут сюда:

• •самая длинная возрастающая подпоследовательность
• •самая длинная общая подпоследовательность двух строк
• •минимум правок, чтобы превратить одну строку в другую
• •сохранить относительный порядок, можно пропускать элементы
• •diff или выравнивание двух последовательностей

DP над подпоследовательностями (LIS / LCS / расстояние редактирования): с чем путают?

• Динамическое программирование (1-D) (Dynamic programming (1-D)): Там хватает одного индекса. Сравнению двух последовательностей нужны два.
• DP на строках (word break) (DP on strings (word break)): Та страница режет одну строку на куски. Эта выравнивает две последовательности.
• Бинарный поиск (массив) (Binary search (array)): Версия возрастающей подпоследовательности за n log n использует бинарный поиск. Табличная версия медленнее.
• Два указателя (в одну сторону) (Two pointers (same direction)): Проверке, является ли строка подпоследовательностью, таблица не нужна. Поиску наибольшей общей нужна.

DP над подпоследовательностями (LIS / LCS / расстояние редактирования): частые ошибки

• Путают подпоследовательность и подстроку

  Подпоследовательность может пропускать элементы, подстрока нет. Переход у них разный.

• Ошибаются на единицу между таблицей и строкой

  Ячейка i указывает на символ с индексом i минус один. Их смешение сдвигает все сравнения.

• Заполняют базовую строку нулями

  Расстояние редактирования начинается со стоимости удаления целого префикса. Нули там дают неверный ответ.

• Берут таблицу при большом n

  O(n в квадрате) умирает на 1e5 элементов. У возрастающей подпоследовательности есть форма за n log n.

DP над подпоследовательностями (LIS / LCS / расстояние редактирования): задачи с собеседований

• Наибольшая общая подпоследовательность: Чистая форма для двух последовательностей.
• Расстояние редактирования: Выбор идёт из трёх соседей, а не из двух.
• Наибольшая возрастающая подпоследовательность: Одна последовательность, сравниваемая сама с собой.
• Удаления для двух строк: Общая длина минус удвоенная общая подпоследовательность.
• Число различных подпоследовательностей: Считается количество способов, а не длина.
• Чередование строк: Два источника, питающие одну целевую строку.
• Кратчайшая общая надпоследовательность: Ответ восстанавливают, идя по таблице назад.

DP над подпоследовательностями (LIS / LCS / расстояние редактирования): сложность по времени и памяти

O(n^2)/O(nm)

Последовательности длины n и m дают O(nm) времени и памяти. Хранение одной строки снижает память до O(m).