algorithm - 最长回文子序列(dp解法)

Question

在这道题的几种dp解法中，比较简单的解法是将给定的字符串反转，计算原串和反转串的LCS。

我的问题是这种方法每次都会产生正确的结果吗？
例如，ACBAC 及其反向CABCA 的最长公共(public)子序列是ABC，这不是回文，但这仍然给出正确的结果由于其他LCS是回文ACA, CAC。

那么，即使可能存在非回文 LCS，这种方法每次都会产生正确的结果吗？

dp 表，如果有帮助的话。

    A C B A C
  0 0 0 0 0 0 
C 0 0 1 1 1 1 
A 0 1 1 1 2 2 
B 0 1 1 2 2 2 
C 0 1 2 2 2 3 
A 0 1 2 2 3 3  

Answer 1

是的，这是正确的。以下两个事实暗示了这一点，这两个事实共同暗示了所需的平等。

1. 最长回文子序列至多等于该字符串及其逆序的最长公共(public)子序列。

2. 最长的回文子序列至少与字符串及其逆序的最长公共(public)子序列一样长。

事实 1 很容易证明:字符串的每个回文子序列当然是子序列，并且它是字符串反向的子序列，因为 S1 是 S2 的子序列当且仅当 reverse(S1) 是 reverse 的子序列(S2)，回文序列的逆序就是它本身。

事实 2 更微妙。我们认为，给定字符串及其反向的 LCS，我们可以导出两个平均长度等于 LCS 的回文子序列。接下来是一个平均论证，即一个或两个至少一样长。

我会用你的例子来说明构建过程。写下字符串中的公共(public)子序列和索引。

A C B A C
1 2 3 4 5
A   B   C
 \  |  /
  A B C
5 4 3 2 1
C A B C A

我们提取 A (1, 4); B (3, 3); C (5, 2)。我们可以通过获取第一个数字不超过第二个数字的前缀并将其镜像来派生一个回文:1, 3, 4 -> A B A。我们从第二个数字不超过第一个的后缀以镜像方式导出另一个:2, 3, 5 -> C B C。

 A  B  C
 1  3  5
.>>\ />>
   | |
 <</ \<<.
 4  3  2
 A  B  C

观察子序列的每个字母恰好被使用了两次(一个去和一次来，中间除外，它在两个回文中都使用一次)，因此我们对均值的观察成立。