---
title: "DP над подпоследовательностями (LIS / LCS / расстояние редактирования)"
url: https://algopath.pro/ru/patterns/dp-subsequence
language: ru
summary: "Состояние здесь это пара позиций, по одной в каждой последовательности. Каждая ячейка спрашивает, совпали ли эти элементы."
updated: 2026-08-24
---

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

Состояние здесь это пара позиций, по одной в каждой последовательности. Каждая ячейка спрашивает, совпали ли эти элементы.

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

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

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

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

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

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

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

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

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

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

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

- **Динамическое программирование (1-D)** - Там хватает одного индекса. Сравнению двух последовательностей нужны два.
- **DP на строках (word break)** - Та страница режет одну строку на куски. Эта выравнивает две последовательности.
- **Бинарный поиск (массив)** - Версия возрастающей подпоследовательности за n log n использует бинарный поиск. Табличная версия медленнее.
- **Два указателя (в одну сторону)** - Проверке, является ли строка подпоследовательностью, таблица не нужна. Поиску наибольшей общей нужна.

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

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

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

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

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

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

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

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

```javascript
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 / расстояние редактирования): частые ошибки

- **Путают подпоследовательность и подстроку** Подпоследовательность может пропускать элементы, подстрока нет. Переход у них разный.
- **Ошибаются на единицу между таблицей и строкой** Ячейка i указывает на символ с индексом i минус один. Их смешение сдвигает все сравнения.
- **Заполняют базовую строку нулями** Расстояние редактирования начинается со стоимости удаления целого префикса. Нули там дают неверный ответ.
- **Берут таблицу при большом n** O(n в квадрате) умирает на 1e5 элементов. У возрастающей подпоследовательности есть форма за n log n.

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

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

## JavaScript

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

## Python

```python
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)
```

## PHP

```php
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);
}
```