我正试图解决Cormem《算法导论》第三版（第405页）中的一个动态编程问题，该问题要求如下：
回文是一个非空字符串一些读起来相同的字母表向前和向后。示例回文都是长度字符串1、
civic、racecar和aibohphobia（害怕回文）。给出一个有效的算法来查找最长的回文给定输入字符串的子序列。例如，给定输入
character，您的算法应该返回CCD_ 5。
好吧，我可以用两种方法解决：
第一个解决方案：
字符串的最长回文子序列（LPS）就是字符串本身及其反向的最长公共子序列。（我在解决了另一个相关问题后构建了这个解决方案，该问题要求序列的最长递增子序列）。由于它只是一个LCS变体，它还需要O（n²）时间和O（n平方）内存。
第二个解决方案：
第二个解决方案更为详细，但也遵循通用LCS模板。它来自以下复发：
lps(s[i..j]) =
s[i] + lps(s[i+1]..[j-1]) + s[j], if s[i] == s[j];
max(lps(s[i+1..j]), lps(s[i..j-1])) otherwise
计算lps长度的伪代码如下：
compute-lps(s, n):
// palindromes with length 1
for i = 1 to n:
c[i, i] = 1
// palindromes with length up to 2
for i = 1 to n-1:
c[i, i+1] = (s[i] == s[i+1]) ? 2 : 1
// palindromes with length up to j+1
for j = 2 to n-1:
for i = 1 to n-i:
if s[i] == s[i+j]:
c[i, i+j] = 2 + c[i+1, i+j-1]
else:
c[i, i+j] = max( c[i+1, i+j] , c[i, i+j-1] )
如果我想有效地构建lps，它仍然需要O（n²）时间和内存（因为我需要表上的所有单元格）。在分析相关问题时，比如LIS，它可以用LCS以外的方法来解决，比如用较少的内存（LIS可以用O（n）内存来解决），我想知道是否也可以用O的内存来解决它。
LIS通过链接候选子序列来实现这一绑定，但对于回文，这更难，因为这里重要的不是子序列中的前一个元素，而是第一个元素。有人知道是否有可能做到这一点吗？或者之前的解决方案是内存最优的吗？
这是一个非常节省内存的版本。但我还没有证明它总是O(n)内存。（通过预处理步骤，它可以比O(n2) CPU更好，尽管O(n2)是最坏的情况。）
从最左边的位置开始。对于每个位置，跟踪最远点的表，在该表上可以生成长度为1、2、3等的反射子序列。（这意味着我们点左侧的子序列会反射到右侧。）对于每个反射子序列，我们存储一个指向子序列下一部分的指针。
当我们正确地工作时，我们从字符串的RHS到当前元素的任何位置进行搜索，并尝试使用这些匹配来改进我们以前的边界。当我们完成时，我们看到最长的镜像子序列，我们可以很容易地构建最好的回文。
让我们考虑一下character。
- 我们从我们最好的回文是字母"c"开始，我们的镜像子序列是通过位于字符串末端的对
(0, 11)到达的 - 接下来考虑位置1处的"c"。我们的形式为
(length, end, start)的最佳镜像子序列现在是[(0, 11, 0), (1, 6, 1)]。（我将省略你需要生成的链表，以便真正找到回文 - 接下来考虑位置2处的
h。我们不改进边界CCD_ 14 - 接下来考虑位置3处的
a。我们改进了CCD_ 16的界 - 接下来考虑位置4处的
r。我们改进了CCD_ 18的界。（这是链接列表有用的地方
通过列表的其余部分，我们不会改进这组界限。
因此，我们得出的最长镜像列表的长度为2。我们会按照链接列表（我没有在本描述中记录它）找到它是ac。由于该列表的末尾位于(5, 3)位置，我们可以翻转列表，插入字符4，然后附加列表以获得carac。
通常，它将需要的最大存储器是存储最大镜像子序列的所有长度加上存储所述子序列的链表的存储器。通常，这将是一个非常小的内存量。
在传统的内存/CPU权衡中，您可以在时间上对列表O(n)进行一次预处理，以生成特定序列元素出现位置的O(n)大小的数组哈希。这可以让您扫描"使用此配对改进镜像子序列"，而不必考虑整个字符串，对于较长的字符串，这通常会大大节省CPU。
@Luiz Rodrigo问题的第一个解决方案是错误的：字符串及其逆的最长公共子集（LCS）不一定是回文。
例如：对于字符串CBACB，CAB是字符串及其反向的LCS，它显然不是回文。然而，有一种方法可以让它发挥作用。在建立了字符串及其反向的LCS后，取其左半部分（对于奇数长度的字符串，包括中间字符），并用反向的左半部分在右侧进行补码（如果字符串长度为奇数，则不包括中间字符。）。很明显，它将是一个回文，并且可以琐碎地证明它将是字符串的子序列。
对于以上LCS，以这种方式构建的回文将是CAC。