Самая длинная палиндромная подпоследовательность (решение дп)

Question

Среди нескольких решений dp для этого вопроса, более простое решение - обратить заданную строку и вычислить LCS исходной и обращенной строки.

У меня вопрос, будет ли этот подход каждый раз давать правильный результат?
Например, самая длинная общая подпоследовательность ACBAC и ее обратная CABCA равна ABC , который не является палиндромом, но все же дает правильный результат, поскольку другие LCS являются палиндромом ACA, CAC .

Итак, будет ли этот подход правильнымрезультат каждый раз, даже если может существовать непалиндром LCS?

Таблица dp, если это помогает.

    A C B A C
  0 0 0 0 0 0 
C 0 0 1 1 1 1 
A 0 1 1 1 2 2 
B 0 1 1 2 2 2 
C 0 1 2 2 2 3 
A 0 1 2 2 3 3  

Answer 1

Да, это правильно.Это подразумевается следующими двумя фактами, которые вместе подразумевают необходимое равенство.

1. Самая длинная палиндромная подпоследовательность не больше, чем самая длинная общая подпоследовательность строки и ее обратное.

2. Самая длинная палиндромная подпоследовательность по крайней мере равна самой длинной общей подпоследовательности строки и ее обратной последовательности.

Факт 1 легко доказатькаждая палиндромная подпоследовательность строки, конечно, является подпоследовательностью и является подпоследовательностью обратной строки, поскольку S1 является подпоследовательностью S2 тогда и только тогда, когда обратная последовательность (S1) является подпоследовательностью обратной последовательности (S2), а обратная последовательностьПалиндромная последовательность сама по себе.

Факт 2 более тонкий.Мы утверждаем, что, учитывая LCS строки и ее обратное, мы можем вывести две палиндромные подпоследовательности, средняя длина которых равна LCS.Из аргумента усреднения следует, что один или оба имеют длину не менее длины.

Я проиллюстрирую процесс построения на вашем примере.Запишите общую подпоследовательность вместе с индексами в строке.

A C B A C
1 2 3 4 5
A   B   C
 \  |  /
  A B C
5 4 3 2 1
C A B C A

Извлекаем A (1, 4); B (3, 3); C (5, 2).Мы можем получить один палиндром, взяв префикс, в котором первое число не превышает второго, и отразив его: 1, 3, 4 -> A B A.Другое зеркально выводится из суффикса, в котором второе число не превышает первого: 2, 3, 5 -> C B C.

 A  B  C
 1  3  5
.>>\ />>
   | |
 <</ \<<.
 4  3  2
 A  B  C

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