我试图思考这两个问题之间有什么区别
给定一个序列 S
1) 找到 S 的最长回文子序列。
2）找到S的最长子序列，其反向也是S的子序列。这两个子序列可以相同。
原句是：找到S的最长子序列S'，使得有一个与S'相同的子序列和一个与S'相反的子序列。
我为这两个问题推导出的 DP 公式是相同的。
它们实际上是相同的问题吗？我一直在尝试这样想：假设最长的回文子序列是longestP，那么longestP它本身显然是 2) 的可能答案。
2）能否有更长的答案？假设有一个，叫做longerP，那么它的逆也是longerPS 的一个子序列，叫做 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 不能是回文数的限制。