题目描述
这是 LeetCode 上的 516. 最长回文子序列 ，难度为 中等。
Tag : 「动态规划」、「区间 DP」
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入：s = "bbbab" 输出：4 解释：一个可能的最长回文子序列为 "bbbb" 。 复制代码
示例 2：
输入：s = "cbbd" 输出：2 解释：一个可能的最长回文子序列为 "bb" 。 复制代码
提示：
- 1 <= s.length <= 1000
- s 仅由小写英文字母组成
动态规划
这是一道经典的区间 DP 题。
之所以可以使用区间 DP 进行求解，是因为在给定一个回文串的基础上，如果在回文串的边缘分别添加两个新的字符，可以通过判断两字符是否相等来得知新串是否回文。
也就是说，使用小区间的回文状态可以推导出大区间的回文状态值。
从图论意义出发就是，任何一个长度为 lenlen 的回文串，必然由「长度为 len - 1len−1」或「长度为 len - 2len−2」的回文串转移而来。
两个具有公共回文部分的回文串之间存在拓扑序（存在由「长度较小」回文串指向「长度较大」回文串的有向边）。
通常区间 DP 问题都是，常见的基本流程为：
- 从小到大枚举区间大小 lenlen
- 枚举区间左端点 ll，同时根据区间大小 lenlen 和左端点计算出区间右端点 r = l + len - 1r=l+len−1
- 通过状态转移方程求 f[l][r]f[l][r] 的值
因此，我们 定义 f[l][r]f[l][r] 为考虑区间 [l, r][l,r] 的最长回文子序列长度为多少。
不失一般性的考虑 f[l][r]f[l][r] 该如何转移。
由于我们的状态定义 没有限制 回文串中必须要选 s[l]s[l] 或者 s[r]s[r]。
我们对边界字符 s[l]s[l] 和 s[r]s[r] 分情况讨论，最终的 f[l][r]f[l][r] 应该在如下几种方案中取 maxmax ：
- 形成的回文串一定不包含 s[l]s[l] 和 s[r]s[r]，即完全不考虑 s[l]s[l] 和 s[r]s[r]：
f[l][r] = f[l + 1][r - 1]f[l][r]=f[l+1][r−1]
- 形成的回文串可能包含 s[l]s[l]，但一定不包含 s[r]s[r]：
f[l][r] = f[l][r - 1]f[l][r]=f[l][r−1]
- 形成的回文串可能包含 s[r]s[r]，但一定不包含 s[l]s[l]：
f[l][r] = f[l + 1][r]f[l][r]=f[l+1][r]
- 形成的回文串可能包含 s[l]s[l]，也可能包含 s[r]s[r]，根据 s[l]s[l] 和 s[r]s[r] 是否相等：
f[l][r] = \begin{cases} f[l + 1][r - 1] + 2 & s[l] = s[r] \\ f[l + 1][r - 1] & s[l] \neq s[r] \\ \end{cases}f[l][r]={f[l+1][r−1]+2f[l+1][r−1]s[l]=s[r]s[l]=s[r]
需要说明的是，上述几种情况可以确保我们做到「不漏」，但不能确保「不重」，对于求最值问题，我们只需要确保「不漏」即可，某些状态重复参与比较，不会影响结果的正确性。
一些细节：我们需要特判掉长度为 11 和 22 的两种基本情况。当长度为 11 时，必然回文，当长度为 22 时，当且仅当两字符相等时回文。
代码：
class Solution { public int longestPalindromeSubseq(String s) { int n = s.length(); char[] cs = s.toCharArray(); int[][] f = new int[n][n]; for (int len = 1; len <= n; len++) { for (int l = 0; l + len - 1 < n; l++) { int r = l + len - 1; if (len == 1) { f[l][r] = 1; } else if (len == 2) { f[l][r] = cs[l] == cs[r] ? 2 : 1; } else { f[l][r] = Math.max(f[l + 1][r], f[l][r - 1]); f[l][r] = Math.max(f[l][r], f[l + 1][r - 1] + (cs[l] == cs[r] ? 2 : 0)); } } } return f[0][n - 1]; } } 复制代码
- 时间复杂度：O(n^2)O(n2)
- 空间复杂度：O(n^2)O(n2)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.516 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
