Как решить задачу от яндекса "НОП с восстановлением ответа"?

есть вот такая идея алгоритма (LCS через DP) пусть у нас есть две последовательности:

• A[0...N-1]

• B[0...M-1]

Создаём двумерный массив dp[N+1][M+1], где:

• dp[i][j] — длина наибольшей общей подпоследовательности между A[0:i] и B[0: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])

Если говорить о полном коде, могу привести пример на Python

def lcs(A, B):
    # Получаем длины последовательностей A и B
    N = len(A)
    M = len(B)
    
    # Создаем двумерный массив dp размером (N+1) x (M+1), и инициализируем его нулями
    # dp[i][j] будет хранить длину наибольшей общей подпоследовательности для первых i элементов A и первых j элементов B
    dp = [[0] * (M + 1) for _ in range(N + 1)]

    # Заполняем таблицу dp с использованием динамического программирования
    for i in range(1, N + 1):  # Перебираем элементы последовательности A
        for j in range(1, M + 1):  # Перебираем элементы последовательности B
            if A[i - 1] == B[j - 1]:  # Если текущие элементы равны
                # Значение dp[i][j] равно dp[i-1][j-1] + 1 (прибавляем этот общий элемент)
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                # Иначе выбираем максимальную длину из предыдущих вариантов
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    # Восстанавливаем саму наибольшую общую подпоследовательность
    i, j = N, M  # Начинаем с конца таблицы
    result = []  # Список для хранения элементов LCS

    while i > 0 and j > 0:  # Пока не достигнем начала таблицы
        if A[i - 1] == B[j - 1]:  # Если элементы на текущих позициях равны
            result.append(A[i - 1])  # Добавляем элемент в результат
            i -= 1  # Переходим к предыдущему элементу в A
            j -= 1  # Переходим к предыдущему элементу в B
        elif dp[i - 1][j] >= dp[i][j - 1]:  # Если длина LCS без элемента B[j-1] больше или равна
            i -= 1  # Переходим к предыдущему элементу в A
        else:  # Если длина LCS без элемента A[i-1] больше
            j -= 1  # Переходим к предыдущему элементу в B

    # Поскольку мы восстанавливаем последовательность с конца, нужно перевернуть результат
    return result[::-1]

# Ввод данных
N = int(input())  # Длина первой последовательности
A = list(map(int, input().split()))  # Первая последовательность
M = int(input())  # Длина второй последовательности
B = list(map(int, input().split()))  # Вторая последовательность


print(*lcs(A, B))

Обозначим s и t строки для которых ищется наибольшая общая подпоследовательность / longest common subsequence:
s состоит из символов s_i, где 1 ≤ i ≤ m, m – длина строки s.
t состоит из символов t_j, где 1 ≤ j ≤ n, n – длина строки t.

Нотация s_[1,i] обозначает префикс строки s длиной i. Аналогично вводится t_[1,j] – префикс t.

s_[1,0] и t_[1,0] – пустые строки.

Даны два префикса s_[1,i] и t_[1,j]. Нас интересует длина наибольшей общей подпоследовательности, которую обозначим f_i,j.

Какие есть свойства у f?

1. f_i,0 = f_0,j = 0 – у любой строки нет ничего общего с пустой строкой, поэтому нули.

2. f_i+1,j ≥ f_i,j, f_i,j+1 ≥ f_i,j – монотонность. Чем длиннее префикс тем длиннее (не короче) общая часть. От добавления новых символов решение укоротиться не может.

3. f_i-1,j-1 ≥ f_i,j - 1 – f растёт не слишком быстро. Если оба префикса укоротить на один символ, то из общей последовательности может удалиться один последний символ, не больше.

4. если s_i = t_j то f_i,j = f_i-1,j-1 + 1. Если символы равны, то к длиннейшей подпоследовательности (f_i-1,j-1) добавляется единица (символ равный s_i и t_j). Двойка и больше добавиться не может из-за свойства 3.

5. если s_i ≠ t_j то f_i,j = f_i-1,j или f_i,j = f_i,j-1. Если символы не равны, то длиннейшая последовательность не может заканчиваться одновременно на s_i и на t_j.
   Если она заканчивается не на s_i, то f_i,j = f_i-1,j, так как символ s_i можно отбросить без ущерба для длины решения.
   Если она заканчивается не на t_j, то f_i,j = f_i,j-1, так как символ t_j можно отбросить без ущерба для длины решения.

Собирая вместе свойства 1, 4, 5 получим формулу:

• f_i,j = 0, если i = 0 или j = 0 (свойство 1);

• f_i,j = f_i-1,j-1 + 1, если i, j > 0 и s_i = t_j (свойство 4);

• f_i,j = max(f_i-1,j, f_i,j-1), если i, j > 0 и s_i ≠ t_j (свойство 5).

Формула позволяет вычислить f_i,j если известны значения f_i-1,j, f_i,j-1, f_i-1,j-1. Сложность вычисления f_i,j и по времени и по памяти O(ij). Сложность по памяти можно сократить до O(min(i, j)) если требуется вычислить только длину. Если кроме длины нужно предъявить общую последовательность, то придётся хранить все значения f.

Восстанавливается подпоследовательность от конца к началу.

Из позиции (i, j) надо перейти в позицию

• (i - 1, j - 1), если i, j > 0 и s_i = t_j;
• (i - 1, j), если i, j > 0 и s_i ≠ t_j и f_i,j = f_i-1,j;
• (i, j - 1), если i, j > 0 и s_i ≠ t_j и f_i,j = f_i,j-1.

Если i = 0 или j = 0, поиск завершается. Каждый раз, когда на маршруте было равенство s_i = t_j, соответствующий символ записывается в ответ. В конце ответ надо будет перевернуть задом наперёд. Или, если хотите избежать переворота, с самого начала стройте подпоследовательность из конца строк s и t в начало.