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

Question

这是算法书(作者 Vazirani)中的问题 (6.7 ch6)，它与 ​​finding longest palindrome 的经典问题略有不同。 .我该如何解决这个问题？

A subsequence is palindromic if it is the same whether read left to right or right to left. For instance, the sequence

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

has many palindromic subsequences, including A,C,G,C,A and A,A,A,A (on the other hand, the subsequence A,C,T is not palindromic). Devise an algorithm that takes a sequence x[1 ...n] and returns the (length of the) longest palindromic subsequence. Its running time should be O(n^2)

Answer 1

这可以使用动态规划在 O(n^2) 中解决。基本上，问题是关于使用 x[i+1...j] 的最长子序列构建 x[i...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] 表。

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

---