가장 긴 회문의 서브는 내가 S의 가장 긴 회문의 순서를 검색) 시퀀스 1 S</p> <p>을 감안할 때 이러한 두 가지 문제</p> <p>의 차이가 무엇인지 생각하기 위해 노력하고있어 서브 순서

Question

입니다

2) 역순이 S의 서브 시퀀스 인 S의 가장 긴 서브 시퀀스를 찾습니다. 두 개의 서브 시퀀스는 동일 할 수 있습니다.
원본 구는 다음과 같습니다. S '와 동일한 서브 시퀀스와 S'의 역순 인 서브 시퀀스가 ​​있도록 S의 가장 긴 서브 시퀀스 S '를 찾습니다.

두 가지 문제점에 대해 유도 된 DP 공식은 동일합니다.

실제로 같은 문제입니까? 나는 이런 식으로 생각하려고 노력했다 : 가장 긴 회문 하위 시퀀스가 ​​longestP이라고 가정하면 longestP 그 자체가 분명히 2)의 가능한 대답이다.

2)에 대한 답변이 더 오래있을 수 있습니까? longerP이라고하는 하나가 있다고 가정하면 longerP의 역 또한 S의 하위 시퀀스이므로 reverseLongerP이라고 부릅니다. 겹쳐서 또는 붙들지 않고, 더 긴 palindrome는 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는 회문 제한이어야하며, 이는 회문 제한이 될 수 없습니다.

Answer 1

좋아, 내가 틀렸어. s와 reverse_of_s가 palindrome을 형성 할 수 있다는 보장은 없습니다. 이것을 보는 것은 정말로 쉽지만 나는 틀린 가정에 갇혀있었습니다. 4 3 1 2 3 4 2 1이 좋은 예입니다.