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

O(n^2)/O(nm)

Отслеживайте лучшую подпоследовательность, заканчивающуюся в каждой позиции: dp[i] для LIS смотрит назад на каждый более ранний меньший элемент, dp[i][j] для LCS или расстояния редактирования проходит 2-D сетку по обеим строкам. Ответ сохраняет относительный порядок, но может пропускать элементы.

Сигналы

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

Шаблон

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

Похоже, но не то

Динамическое программирование (1-D): Обычное 1-D dp[i] хранит одно текущее состояние на индекс, например лучшую сумму, заканчивающуюся здесь. DP над подпоследовательностями вместо этого отслеживает позиции сразу в одной или двух ПОСЛЕДОВАТЕЛЬНОСТЯХ (LIS хранит длину, заканчивающуюся в индексе i, LCS и расстояние редактирования требуют 2-D сетку по обеим строкам), потому что ответ зависит от того, какие более ранние элементы были выбраны, а не только от позиции.

n до ~1e3..1e4 для O(n^2) таблицы LIS, либо n, m до ~1e3 каждая для O(nm) сетки LCS/расстояния редактирования -> квадратичное время; для чистого LIS patience sorting снижает его до O(n log n).

Изучить этот паттерн