算法导论 — 思考题15-2 最长回文子序列

（最长回文子序列）回文(palindrome)是正序与逆序相同的非空字符串。例如，所有长度为1的字符串、civic、racecar、aibohphobia都是回文。设计高效算法，求给定输入字符串的最长回文子序列。例如，给定输入character，算法应该返回carac。算法的运行时间是怎样的？
　　
　　解
　　假设有一个字符串$S[1..n] = {s_1, s_2, …, s_n}$S[1..n]=s1​,s2​,…,sn​，$P[1..k] = {p_1, p_2, …, p_k}$P[1..k]=p1​,p2​,…,pk​是$S$S的任意最长回文子序列(Longest Palindrome Subsequence, LPS)。
　　比较首字符$s_1$s1​和尾字符$s_n$sn​，可以分以下3种情况：
　　1) 如果$s_1 = s_n$s1​=sn​，则有$p_1 = s_1$p1​=s1​和$p_k = s_n$pk​=sn​，并且$P[2..k-1]$P[2..k−1]是$S[2..n-1]$S[2..n−1]的一个LPS；
　　2) 如果$s_1 ≠ s_n$s1​̸​=sn​，那么$s_1 ≠ p_1$s1​̸​=p1​意味着$P[1..k]$P[1..k]是$S[2..n]$S[2..n]的一个LPS；
　　3) 如果$s_1 ≠ s_n$s1​̸​=sn​，那么$s_n ≠ p_k$sn​̸​=pk​意味着$P[1..k]$P[1..k]是$S[1..n-1]$S[1..n−1]的一个LPS。
　　需要补充说明一下。根据上文第(1)点给出的结论，如果$s_1 = s_n$s1​=sn​，只需要求解$S[2..n-1]$S[2..n−1]的LPS，并将$s_1$s1​和$s_n$sn​分别加到$S[2..n-1]$S[2..n−1]的LPS的头部和尾部，从而得到$S[1..n]$S[1..n]的一个回文子序列，我们假设这个回文子序列的长度为$l_1$l1​。然而，严格来说，还需要求解$S[1..n-1]$S[1..n−1]和$S[2..n]$S[2..n]的LPS，它们也是$S[1..n]$S[1..n]的回文子序列，假设这两个LPS的长度分别为$l_2$l2​和$l_3$l3​。我们需要比较$l_1$l1​、$l_2$l2​、$l_3$l3​的大小，其中最大者对应的回文子序列才是$S[1..n]$S[1..n]的LPS。然而，上文第(1)点为何断言$l_1$l1​一定是最大的？我们采用反证法来说明。
　　假设$l_1 &lt; l_2$l1​<l2​，并假设$S[2..n-1]$S[2..n−1]的LPS的长度为$l_4$l4​，有$l_1 = l_4 + 2$l1​=l4​+2。如果$S[1..n-1]$S[1..n−1]的LPS不包含$s_1$s1​，那么将$s_1$s1​从$S[1..n-1]$S[1..n−1]中去掉，$S[1..n-1]$S[1..n−1]的LPS实际上也是$S[2..n-1]$S[2..n−1]的LPS，故$l_2 = l_4$l2​=l4​，于是有$l_1 = l_2 + 2 &gt; l_2$l1​=l2​+2>l2​。这与$l_1 &lt; l_2$l1​<l2​矛盾。
　　如果$S[1..n-1]$S[1..n−1]的LPS包含$s_1$s1​，那么$S[1..n-1]$S[1..n−1]的LPS的尾字符一定等于$s_1$s1​，将$S[1..n-1]$S[1..n−1]的LPS的首尾字符去掉，得到的子序列一定是$S[2..n-1]$S[2..n−1]的一个回文子序列（假设它的长度为$l_5$l5​，有$l_2 = l_5 + 2$l2​=l5​+2），并且一定有$l_4 ≥ l_5$l4​≥l5​，故$l_1 = l_4 + 2 ≥ l_5 + 2 = l_2$l1​=l4​+2≥l5​+2=l2​，这也与$l_1 &lt; l_2$l1​<l2​矛盾。故$l_1 ≥ l_2$l1​≥l2​是一定成立的。
　　同理，$l_1 ≥ l_3$l1​≥l3​也是成立的。综上所述，上文结论(1)是对的。
　　可以看到，LPS问题与最长公共子序列问题是很类似的，也具有最优子结构。
　　• 如果$s_1 = s_n$s1​=sn​，那么需要求解子问题$S[2..n-1]$S[2..n−1]的LPS，并将$s_1$s1​和$s_n$sn​分别加到$S[2..n-1]$S[2..n−1]的LPS的头部和尾部，从而得到$S[1..n]$S[1..n]的LPS
　　• 如果$s_1 ≠ s_n$s1​̸​=sn​，那么需要分别求解两个子问题$S[2..n]$S[2..n]和$S[1..n-1]$S[1..n−1]的LPS，二者中较长者即为$S[1..n]$S[1..n]的LPS。
　　用$c[i, j]$c[i,j]表示子序列$S[i, j]$S[i,j]的LPS的长度，可以得到以下递归式：
　　　　　　　　
　　我们可以自下而上的求解最长回文子序列问题。下面给出该算法的伪代码。
　　
　　与LCS类似，LPS的时间复杂度为$Θ(n_2)$Θ(n2​)。下图展示了对字符串character运行了LPS-LENGTH的结果。
　　
　　本节相关的code链接。
　　https://github.com/yangtzhou2012/Introduction_to_Algorithms_3rd/tree/master/Chapter15/Problems/Problem_15-2