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

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

Для одной последовательности dp[i] это самая длинная возрастающая цепочка, которая кончается на элементе i. Каждое dp[i] начинается с 1: элемент сам по себе.

Для каждого i просмотрите все предыдущие j. Если arr[j] меньше, цепочка на j может взять arr[i] следующим.

Тогда dp[i] становится большим из самого себя и dp[j] плюс один. Ответ это наибольшее dp[i], а не последнее.

Для двух последовательностей строят таблицу. Ячейка i и j это ответ для этих двух префиксов.

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

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

Источники: Википедия: Наибольшая общая подпоследовательность, Википедия: Расстояние Левенштейна, Wagner, Fischer (1974), The string-to-string correction problem (англ.)

1. arr = [2, 5, 3, 7, 4, 8], все dp = 1Каждый элемент сам по себе это цепочка длины 1.
2. dp[1] = 2, dp[2] = 2И 5, и 3 могут идти после 2. Других меньших элементов перед ними нет.
3. dp[3] = 37 может идти после 5 или 3, у обоих dp равно 2. Прибавляем один.
4. dp[4] = 34 может идти после 3, но не после 5 или 7. Значит оно продолжает 2, 3.
5. dp = [1, 2, 2, 3, 3, 4], ответ = 48 может идти после любого элемента. Одна из самых длинных цепочек это 2, 5, 7, 8.

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;
}

function longestIncreasingSubsequence(arr: number[]): number {
    const dp = new Array<number>(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;
}

def longest_increasing_subsequence(arr):
    if not arr:
        return 0
    dp = [1] * len(arr)
    for i in range(1, len(arr)):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

function longestIncreasingSubsequence(array $arr): int {
    $n = count($arr);
    if ($n === 0) return 0;
    $dp = array_fill(0, $n, 1);
    for ($i = 1; $i < $n; $i++) {
        for ($j = 0; $j < $i; $j++) {
            if ($arr[$j] < $arr[$i]) {
                $dp[$i] = max($dp[$i], $dp[$j] + 1);
            }
        }
    }
    return max($dp);
}

    public static int longestIncreasingSubsequence(int[] arr) {
        int[] dp = new int[arr.length];
        Arrays.fill(dp, 1);
        int best = arr.length > 0 ? 1 : 0;
        for (int i = 1; i < arr.length; i++) {
            for (int 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;
    }

    public static int LongestIncreasingSubsequence(int[] arr) {
        var dp = new int[arr.Length];
        Array.Fill(dp, 1);
        int best = arr.Length > 0 ? 1 : 0;
        for (int i = 1; i < arr.Length; i++) {
            for (int 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 / расстояние редактирования): когда применять?

Паттерн «DP над подпоследовательностями (LIS / LCS / расстояние редактирования)» нужен, когда в условии есть слова «самая длинная возрастающая подпоследовательность», «самая длинная общая подпоследовательность двух строк» или «минимум правок, чтобы превратить одну строку в другую». Решение на нём обычно укладывается в O(n^2)/O(nm).

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

Слова в условии для всех паттернов собраны в одной таблице: шпаргалка по паттернам алгоритмов.

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

Паттерн «DP над подпоследовательностями (LIS / LCS / расстояние редактирования)» чаще всего путают с этими паттернами: Динамическое программирование (1-D), DP на строках (word break), Бинарный поиск (массив) и Два указателя (в одну сторону).

• Динамическое программирование (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 / расстояние редактирования)» решает такие задачи с собеседований: Наибольшая общая подпоследовательность, Расстояние редактирования, Наибольшая возрастающая подпоследовательность, Удаления для двух строк, Число различных подпоследовательностей, Чередование строк и Кратчайшая общая надпоследовательность.

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

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

У паттерна «DP над подпоследовательностями (LIS / LCS / расстояние редактирования)» целевая сложность O(n2)/O(nm).

Одна последовательность из n элементов стоит O(n²) времени. Две длины n и m стоят O(nm), и хватает одной строки памяти.