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

Module 1: 2D DP

Наибольшая общая подпоследовательность (НОП)
Наибольшая возрастающая подпоследовательность (НВП)
Наибольшая возрастающая подпоследовательность (НВП) за $O(N \log N)$
Задача рюкзака
Lazy DP

Module 2: DSU

Система непересекающихся множеств

Module 3: MST

Минимальные и максимальные остовные деревья
Kruskal's Algorithm
Алгоритм Прима
Алгоритм Борувки

Module 4: Combinatorics

Звезды и столбцы
Принцип включения-исключения

Module 5: Geometry

Нахождение площади простого многоугольника

Module 6: Arbitrary-Precision Arithmetic

Длинная Арифметика

Module 7: Data structures for keeping minimum

Stack with Minimum
Queue with Minimum
Deque with Minimum

Module 8: Heap [BONUS]

Двоичная Куча

Главная Курсы Ресурсы Задачи Национальная олимпиада Соревнования Таблица лидеров

...

Главная/Courses/Course 3/Module 1: 2D DP/Наибольшая общая подпоследовательность (НОП)

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

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

Условие задачи

Даны две последовательности $a_1, a_2, \ldots, a_n$ и $b_1, b_2, \ldots, b_m$ . Требуется найти длину наибольшей общей подпоследовательности.

Up next

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

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

b1,b2,…,bm

Например, наибольшая общая подпоследовательность $[1, 2, 3]$ и $[2, 3, 1]$ является $[2, 3]$ .

Решение

Обозначим как $dp(i, j)$ решение для префикса $a$ длины $i$ и префикса $b$ длины $j$ . Т.е. длину наибольшей общей подпоследовательности $a[1 \ldots i]$ и $b[1 \ldots j]$ .

Базовые случаи это:

dp(0, j) = 0 \ (0 \leq j \leq m)

dp(i, 0) = 0 \ (0 \leq i \leq n)

Попытаемся теперь найти переходы для общего случая $dp(i, j) \ (0 < i \leq n, \ 0 < j \leq m)$ . Давайте разберем переходы:

Элемент $a_i$ не включен в общей подпоследовательности. Тогда имеем переход $dp(i - 1, j)$ .
Элемент $b_j$ не включен в общей подпоследовательности. Тогда имеем переход $dp(i, j - 1)$ .
Элементы $a_i$ и $b_j$ включены в общей подпоследовательности. Такое возможно только в случае если они равны, т.е. $a_i=b_j$ . Тогда имеем переход .

Следовательно, имеем формулу:

dp(i, j) = \text{max} \begin{cases} dp(i - 1, j) \\ dp(i, j - 1) \\ dp(i - 1, j - 1) + 1 & a_i = b_j \\ \end{cases}

НОП с восстановлением

Давайте для каждой не базовой состояний запомним наилучший переход. Т.е. мы знаем, что $dp(i, j)$ имеет три разных перехода:

$dp(i - 1, j)$
$dp(i, j - 1)$
$dp(i - 1, j - 1) + 1)$

Создадим другой массив $p(i, j)$ и сохраним в $p(i, j)$ какой переход наилучший для $d(i, j)$ . Например, если $dp(i, j) = dp(i - 1, j - 1) + 1$ то тогда имеем $p(i, j) = 3$ .

После этого теперь мы можем восстановить ответ. Инициализируем $x=n, y=m$ и делаем следующее до тех пор, пока $x>0$ и $y>0$ .

Если $p(x, y) == 3$ то мы включали в общее подпоследовательность $a_x$ и $b_y$ . Следовательно, добавляем $a_x$ в ответ и переходим в $:x=x-1, y:=y-1$ .
Если $p(x, y) == 2$ то переходим в $x,y:=y-1$ .
Если $p(x, y) == 1$ то переходим в $x:=x-1,y$ .

bj

dp(i - 1, j - 1) + 1

=

bj

for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = 0;
            dp[i][j] = max(dp[i][j], dp[i - 1][j]);
            dp[i][j] = max(dp[i][j], dp[i][j - 1]);
            if (a[i] == b[j]) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
            }
        }
    }

for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = -1;
            if (dp[i - 1][j] > dp[i][j]) {
                dp[i][j] = dp[i - 1][j];
                p[i][j] = 1;
            }
            if (dp[i][j - 1] > dp[i][j]) {
                dp[i][j] = dp[i][j - 1];
                p[i][j] = 2;
            }
            if (a[i] == b[j] && dp[i - 1][j - 1] + 1 > dp[i][j]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                p[i][j] = 3;
            }
        }
    }
    vector<int> res;
    int x = n, y = m;
    while (x > 0 && y > 0) {
        if (p[x][y] == 3) {
            res.push_back(a[x]);
            x -= 1;
            y -= 1;
        } else if (p[x][y] == 2) {
            y -= 1;
        } else { // p[x][y] == 1
            x -= 1;
        }
    }
    reverse(res.begin(), res.end());