最长的回文序列(dp解决方案)

Question

在这个问题的几个dp解决方案中,一个更简单的解决方案是反转给定的字符串并计算原始和反向字符串的LCS.

我的问题是这种方法每次会产生正确的结果吗？
例如,ACBAC及其反向CABCA的最长公共子序列是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很容易证明：字符串的每个回文子序列当然都是子序列，并且它是字符串反向的子序列，因为当且仅当reverse（S1）是反向的子序列（S2）时，S1才是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

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