可以使用动态编程在O（n ^
2）中解决。基本上，这个问题是关于建设最长的回文序列x[i...j]使用最长的子序列x[i+1...j]，x[i,...j-1]以及x[i+1,...,j-1]（如果第一个和最后一个字母相同）。

首先，空字符串和单个字符串通常是回文。请注意，对于一个子字符串x[i,...,j]，如果x[i]==x[j]可以说，最长回文的长度是上的最长回文x[i+1,...,j-1]+2。如果它们不匹配，最长的回文是最大的那个的x[i+1,...,j]和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

您可以简单地实现该功能的记忆版本，或编写一个自下而上的longest [i] [j]表。

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