[LeetCode]Longest Palindromic Subsequence

用DP[i][j]表示string在[i, j]范围内的最长subsequence，那么我们可以得到递推方程：

• DP[i][j] = DP[i + 1][j - 1] + 2, s[i] == s[j]
• DP[i][j] = max(DP[i + 1][j], DP[i][j - 1]), s[i] != s[j]

我们还要initialize区间长度为1和2的初始情况。时间复杂度O(n^2), 空间复杂度O(n^2)，代码如下：

这道题也可以转化为LCS(Longest Common Subsequence)问题。我们用LPS表示Longest Palindromic Subsequence，对于输入字符串s，假设s' = reverse(s)，那么LPS(s) = LCS(s, s')。值得注意的是这个结论对Longest Common Substring和Longest Palindromic Substring是不成立的，我们可以轻易举出反例，比如s = abcdxxydcba，s' = abcdyxxdcba，Longest Common Substring的长度为4(abcd)，但是Longest Palindromic Substring的长度只有2，是xx。对于Subsequence来说，反例却并不容易找，我们最多找到和LPS 长度相同的非回文的LCS，比如s = acbac，s' = cabca，LPS和LCS的长度都为3。但是我们永远可以找到和LPS长度一样的回文Common Subsequence并且其长度为LCS(s, s')，为了证明这一点，我们需要证明len(LPS) = len(LCS)。(以下证明参考这篇文章)
显而易见的，len(LPS) <= len(LCS)，LPS肯定是s和s'的CS(Common Subsequence)。我们接下来证明len(LPS) >= len(LCS)，假设s长度为n，t为LCS(s, s')，长度为m。我们假设t为奇数，t[k]为LCS的中点，并且t[k]和s[i]以及s'[j]匹配：

• s被分成了两部分sl = s[0:i - 1], sr = s[i + 1:n]
• s'被分成了两部分s'l = s'[0, j - 1], s'r = s[j + 1, n]
• t被分成了两部分tl = t[0:k - 1], tr = t[k + 1, m]
• LCS(s1, s'l) = tl, LCS(sr, s'r) = tr

假设s'r是reverse(sl)的后缀，我们可以得到以下结论：

1. sr是reverse(s'l)的后缀
2. 因为tr是sr和s'r的LCS，根据上面的假设和结论，其必为reverse(s'l)和reverse(sl)的CS
3. 那么reverse(tr)就是s'l和sl的CS
4. 我们构建出t' = reverse(tr) + t[k] + tr，其肯定是回文。根据以上推论，其为sl + sr和s'l + s'r，也就是s和s'的PS(Palindromic Subsequence)，而t'的长度和t是一样的(k为t的中点)，t为LCS(s, s')，也就是说len(LPS) >= len(LCS)。

另一种情况就是reverse(sl)是s'r的后缀，我们仿照上面的思路也可以得到一下结论：

1. reverse(s'l)是sr的后缀
2. 因为tl是sl和s'l的LCS，根据上面的假设和结论，reverse(tl)必为sr和s'r的CS
3. 我们同样可以构建出t' = tl + t[k] + reverse(tl)，其为回文并且是s和s'的PS。t'长度和t一样并且t是LCS，所以len(LPS) >= len(LCS)。

偶数情况的证明类似，这里就继续了。

复杂度和LCS是一样的，时间复杂度O(n^2)，空间复杂度用滚动数组优化到O(n)，代码如下：