最長的迴文子VS最長的序列，其反過來也是一個子

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就是一個很好的例子。