← Назад к ДП

Наибольшая общая подпоследовательность (НОП)

Поиск самой длинной последовательности, общей для двух массивов

🐍 Python
n = int(input())
A = list(map(int, input().split()))
m = int(input())
B = list(map(int, input().split()))

dp = [[0] * (m + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    for j in range(1, m + 1):
        if A[i - 1] == B[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

print(dp[n][m])
⚙️ C++
#include <bits/stdc++.h>
using namespace std;
using T = long long;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    T n, m;
    cin >> n;
    vector<T> A(n);
    for (T i = 0; i < n; i++)
        cin >> A[i];
    
    cin >> m;
    vector<T> B(m);
    for (T i = 0; i < m; i++)
        cin >> B[i];
    
    vector<vector<T>> dp(n + 1, vector<T>(m + 1, 0));
    
    for (T i = 1; i <= n; i++) {
        for (T j = 1; j <= m; j++) {
            if (A[i - 1] == B[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    
    cout << dp[n][m];
    return 0;
}

Как работает алгоритм НОП?

НОП (Longest Common Subsequence, LCS) — это задача поиска самой длинной последовательности, которая является подпоследовательностью двух заданных последовательностей (массивов или строк).

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

Основная идея динамического программирования

Пусть dp[i][j] — длина наибольшей общей подпоследовательности для первых i элементов массива A и первых j элементов массива B.

Рекуррентная формула:

Базовый случай: dp[0][j] = dp[i][0] = 0 (пустая подпоследовательность)

Временная сложность: O(n × m) — два вложенных цикла.

Пространственная сложность: O(n × m) — матрица dp.

Пример работы

Рассмотрим два массива:

A = [1, 3, 4, 5, 2] (n=5)

B = [2, 4, 3, 5, 1] (m=5)

Таблица dp:

      ∅  2  4  3  5  1
   ∅  0  0  0  0  0  0
   1  0  0  0  0  0  1
   3  0  0  0  1  1  1
   4  0  0  1  1  1  1
   5  0  0  1  1  2  2
   2  0  1  1  1  2  2

Ответ: dp[5][5] = 2

Длина наибольшей общей подпоследовательности: 2
Примеры подпоследовательностей: [3, 5], [4, 5], [1] и т.д.

Визуализация заполнения таблицы

Алгоритм заполняет таблицу построчно:

В конце ответ находится в правом нижнем углу — dp[n][m].

Попробовать алгоритм онлайн

Введите два массива и найдите длину НОП:

Результат появится здесь...