如何解决 Yandex 任务“NOP 带答案恢复”？

有这样一个算法的思路（LCS via 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为要寻找最长公共子序列的字符串：s由符号s i组成_，其中1 ≤ i ≤ m，m是字符串s的长度。t由字符t _j组成，其中1 ≤ j ≤ n，n是字符串t的长度。

符号s _[1,i]表示长度为i的字符串s的前缀。类似地，引入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 )加 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 放在一起，我们得到公式：

• 如果i = 0或_j = 0，则f i, 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-1,j、f _i,j-1、f _{i-1,j-1 的}值，该公式使我们能够计算f _i,j。计算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的末尾开始构建子序列。