Решение задачи #6 на Python с Яндекс CodeRun — НОП с восстановлением ответа

Вариант решения задачи на языке программирования Python с Яндекс CodeRun.
Категория: Алгоритмы.
Название задачи: НОП с восстановлением ответа.
Сложность: Средняя.
Статус решения: "Решено".

Условие задачи:
Даны две последовательности, требуется найти и вывести их наибольшую общую подпоследовательность.

Напомним:
Последовательность xx называется подпоследовательностью последовательности yy, если xx получается из 𝑦y удалением нескольких (возможно, нуля или всех) элементов.

Наибольшая общая подпоследовательность - последовательность наибольшей длины, которая является подпоследовательностью обеих последовательностей.
Формат ввода

В первой строке входных данных содержится число N – длина первой последовательности (1 ≤≤ N ≤≤ 1000). Во второй строке заданы члены первой последовательности (через пробел) – целые числа, не превосходящие 10000 по модулю.

В третьей строке записано число M – длина второй последовательности (1 ≤≤ M ≤≤ 1000). В четвертой строке задаются члены второй последовательности (через пробел) – целые числа, не превосходящие 10000 по модулю.
Формат вывода

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

Решение:

Python

import sys

def main():
    """
    Основная функция для нахождения наибольшей общей подпоследовательности (LCS).
    """
    # Считываем входные данные
    input = sys.stdin.read().splitlines()

    # Длина первой последовательности
    n = int(input[0])
    # Первая последовательность
    seq1 = list(map(int, input[1].split()))

    # Длина второй последовательности
    m = int(input[2])
    # Вторая последовательность
    seq2 = list(map(int, input[3].split()))

    # Инициализация таблицы для динамического программирования
    # dp[i][j] будет содержать длину LCS для seq1[0..i-1] и seq2[0..j-1]
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    # Заполнение таблицы dp
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if seq1[i - 1] == seq2[j - 1]:
                # Если элементы совпадают, увеличиваем длину подпоследовательности
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                # Иначе берём максимум из возможных вариантов
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    # Восстановление наибольшей общей подпоследовательности
    lcs = []
    i, j = n, m
    while i > 0 and j > 0:
        if seq1[i - 1] == seq2[j - 1]:
            # Если символы совпадают, добавляем их в LCS
            lcs.append(seq1[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            # Двигаемся в сторону большего значения в таблице dp
            i -= 1
        else:
            j -= 1

    # Порядок в lcs нужно развернуть, так как мы шли с конца
    lcs.reverse()

    # Выводим наибольшую общую подпоследовательность
    print(" ".join(map(str, lcs)))

if __name__ == "__main__":
    main()

Объяснение кода

Ввод данных:
Считываем размеры и элементы двух последовательностей.

Инициализация таблицы dp:
dp[i][j] хранит длину LCS для первых i элементов первой последовательности и первых j элементов второй последовательности.

Заполнение таблицы dp:
Если элементы совпадают, увеличиваем длину LCS.
Если элементы не совпадают, берем максимум между значениями слева и сверху.

Восстановление LCS:
Начинаем с последней ячейки таблицы dp и идем к началу, выбирая элементы, которые входят в LCS.

Вывод результата:
Порядок LCS восстанавливаем с помощью reverse(), так как элементы добавляются с конца к началу.

Источник решения: hdhai.com