Серия палиндром подпоследовательности VS Longest подпоследовательности которой обратное также подпоследовательности

Question

Я пытаюсь думать, что разница между этими двумя проблемами

Учитывая последовательность S

1) Найти самую длинную палиндром подпоследовательность S

2) Найти самую длинную подпоследовательность S, реверс которой также является подпоследовательностью S. Две подпоследовательности могут быть одинаковыми.
Оригинальная фразировка: Найдите самую длинную подпоследовательность S 'из S, такую, что существует подпоследовательность, такая же, как S', и подпоследовательность, обратная к S '.

Композиции DP, полученные для обеих проблем, одинаковы.

Действительно ли это те же проблемы? Я пытался так думать: Предположим, что самая длинная подпоследовательность палиндрома - longestP, тогда longestP сам по себе является возможным ответом на 2).

Может ли быть более длинный ответ на 2)? Предположим, что существует один, называемый longerP, тогда обратная сторона longerP также является подпоследовательностью S, назовите ее reverseLongerP. С перекрытием или нет, более длинный палиндром может быть построен от longerP и reverseLongerP. Таким образом, противоречит нашему предположению, что longestP является самым длинным палиндром.

Может ли быть более короткий ответ на вопрос 2)? Я так не думаю, так как 2) просит нас найти самую длинную подобласть такого рода, и longestP уже является возможным ответом, любая подпоследовательность, которая меньше, чем longestP, не должна рассматриваться.

Выше моего мышления к этой проблеме, чего-то, что мне не хватает?

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

Мое мышление состоит в том, что предположим, что такая последовательность существует, тогда s и ее обратная сторона могут образовывать палиндром с длиной length_of_s + length_of_reverse_s - length_of_overlap, поэтому минимальная длина этого палиндрома будет length_of_s. Но в этом случае length_of_overlap равен length_of_s, поэтому s и его обратное должны быть одинаковыми, s должен быть палиндром, который нарушил бы s, не может быть ограничением палиндрома.

Answer 1

Хорошо, я получил то место, где я был неправ. Не гарантируется, что s и reverse_of_s могут сформировать палиндром. Это действительно легко увидеть, но я застрял в своем неправильном предположении. 4 3 1 2 3 4 2 1 - хороший пример.