我正在尝试解决Cormem的《算法导论第三版》（第405页）中的动态规划问题，其要求如下：
一个回文串是指某个字母表上的非空字符串，它从前往后读和从后往前读都一样。例如，长度为1的所有字符串、civic、racecar和aibohphobia（对回文串的恐惧）都是回文串。
设计一个高效的算法，找到给定输入字符串中作为子序列的最长回文串。例如，对于输入character，你的算法应该返回carac。
嗯，我可以用两种方法来解决它：
第一种解决方案：
该字符串的最长回文子序列（LPS）只是其本身和其反转的最长公共子序列。 （我在解决另一个相关问题（要求序列的最长递增子序列）后构建了此解决方案）。 由于它只是LCS变体，因此它也需要O（n²）时间和O（n²）内存。
第二个解决方案： 第二个解决方案有点更加详细，但也遵循一般的LCS模板。 它来自以下递归：
计算最长回文子序列长度的伪代码如下：
如果我想有效地构建lps（因为我需要表格上的所有单元格），仍然需要O（n²）的时间和内存。通过分析相关问题，例如LIS，可以使用比LCS类似方法更少的内存来解决（LIS可用O（n）内存解决），我在想是否也可能将其解决为O（n）内存。
LIS通过链接候选子序列实现了这个限制，但对于回文字符串来说，这更难了，因为这里重要的不是子序列中的前一个元素，而是第一个元素。是否有人知道是否可能做到这一点，或者以前的解决方案已经是内存最优的？
一个回文串是指某个字母表上的非空字符串，它从前往后读和从后往前读都一样。例如，长度为1的所有字符串、civic、racecar和aibohphobia（对回文串的恐惧）都是回文串。
设计一个高效的算法，找到给定输入字符串中作为子序列的最长回文串。例如，对于输入character，你的算法应该返回carac。
嗯，我可以用两种方法来解决它：
第一种解决方案：
该字符串的最长回文子序列（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
计算最长回文子序列长度的伪代码如下：
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（n）内存。
LIS通过链接候选子序列实现了这个限制，但对于回文字符串来说，这更难了，因为这里重要的不是子序列中的前一个元素，而是第一个元素。是否有人知道是否可能做到这一点，或者以前的解决方案已经是内存最优的？