LPS: Longest Palindrome Subsequence 最长回文子序列
LCS: Longest Common Subsequence 最长公共子序列

对于一个字符串 abba，它的最长回文子序列就是它本身，它与它的反转abba 的最长公共子序列也是 abba。那么，一个字符串的最长回文子序列是否为该字符串与它的反转的最长公共子序列？

1 LCS的求解方法

一般使用动态规划的方法求解 LCS问题。具体来说，对于字符串 与 ， 定义 表示 与 的最长公共子序列的长度。其中， 表示字符串 的长度为 的前缀。

对于 ，有如下转移：

• ，如果满足
• ，如果不满足

例如，对于字符串 abaacba，其内容如下：

• 红点代表两个字符串对应位置相等，且对应一个字符
• 蓝色线条表示转移方式
• 线条经过的红色点的个数，就是的值
• 将线条经过所有红点对应的字符连起来，就是LCS

图1: 字符串abaacba的DP内容示例

2 LPS与LCS

假设字符串 为 字符串 的反转，假设字符串 的长度为 ，那么

• 
• 如果有 ，有
  • 

该性质对应到 LCS问题中的DP图时，可以看到

• 红点是按照反对角线呈对称分布的
• 对称的红点代表的字符是一样的

如果从反对角线上的某一点（存在蓝色线条通过）出发，分别生成两条路径：

• 第一条路径通往左上角
• 第二条路径通往右下角

两条路径合起来，就是一个 具体的转移方式，是一个 Common Subsequence。而对于某一个点生成的两条路径，假设该路径会经过最多的红点，因为红点是对称的，

• 所以两条路径也是对称的

枚举这样所有的点，求出来的最长的 Common Subsequence，就是两个字符串的 LCS。同时，这条路径是按照反对角线对称的。因此，生成的LCS就是LPS。