如何找到最长的回文子序列？

问题就在这里（6.7ch6 http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf）来自算法书（Vazirani），与经典问题略有不同找到最长的回文 https://stackoverflow.com/questions/1115001/write-a-function-that-returns-the-longest-palindrome-in-a-given-string。我怎么解决这个问题 ？

一个子序列是回文序列，如果它是 无论从左到右阅读还是 右到左。例如， 顺序

A,C,G,T,G,T,C,A,A,A,A,T,C,G

有许多回文子序列， 包括A,C,G,C,A and A,A,A,A（另一方面，子序列A,C,T不是回文）。设计一个 接受序列的算法x[1 ...n]并返回（的长度） 最长回文子序列。它是 运行时间应该是O(n^2)

这可以使用动态规划在 O(n^2) 内解决。基本上，问题是建立最长的回文子序列x[i...j]使用最长的子序列x[i+1...j], x[i,...j-1] and x[i+1,...,j-1]（如果第一个和最后一个字母相同）。

首先，空字符串和单个字符串通常是回文。 请注意，对于子字符串x[i,...,j], if x[i]==x[j]，我们可以说最长回文串的长度是最长回文串的长度x[i+1,...,j-1]+2。如果不匹配，则最长回文数是其中的最大值x[i+1,...,j] and y[i,...,j-1].

这给了我们这个函数：

longest(i,j)= j-i+1 if j-i<=0,
              2+longest(i+1,j-1) if x[i]==x[j]
              max(longest(i+1,j),longest(i,j-1)) otherwise

您可以简单地实现该函数的记忆版本，或者编写一个自下而上的最长[i][j]表。

这仅给出最长子序列的长度，而不是实际的子序列本身。但它也可以很容易地扩展来做到这一点。