私はこれら2つの問題の違いは何かを考えようとしています
与えられた数列 S
1) S の最長回文部分列を見つけます。
2) 逆もまた S のサブシーケンスである S の最長のサブシーケンスを見つけます。2 つのサブシーケンスは同じである可能性があります。
元の言い回しは、S' と同じサブシーケンスと S' の逆のサブシーケンスが存在するように、S の最長サブシーケンス S' を見つけます。
2 つの問題に対して私が導き出した DP の定式化は同じです。
それらは実際に同じ問題ですか？私はこのように考えようとしてきました: 最長の回文サブシーケンスが であると仮定するとlongestP、それlongestP自体は明らかに 2) に対する可能な答えです。
2) に対するより長い答えはありますか? と呼ばれるものがあると仮定するとlongerP、 の逆longerPも S のサブシーケンスであり、それを と呼びますreverseLongerP。longerP重複してもしなくても、とからより長い回文を構築できますreverseLongerP。longestPしたがって、最長の回文であるという私たちの仮定と矛盾します。
2）に対するより短い答えはありますか？longestP2) はそのような種類の最長のサブシーケンスを見つけるように求めており、すでに可能な答えであるため、より短いサブシーケンスは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 が回文であってはならない制限に違反します。