最长回文子序列（dp解法）

Question

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

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

，这仍然给出正确的结果

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

dp table，如果有帮助的话。

    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很容易证明：字符串的每个回文子序列当然是一个子序列，并且它是字符串反向的子序列因为S1是S2的子序列当且仅当reverse(S1)是一个子序列reverse(S2) 的逆序，回文序列的逆序就是它自己。

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

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

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

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

Longest Palindromic Subsequence (dp solution)