LeetCode 516. 最长回文子序列
题目描述
题意分析
从非空字符串中删除若干字符，也可以不删除，要求剩下字符保持原顺序并组成回文，返回能够得到的最大长度。回文表示从左向右读与从右向左读相同。
本题选择的是子序列，字符之间允许有间隔，但不能重排；它不同于必须连续的回文子串。只要求长度，不要求输出具体选中的字符。任意单个字符都构成回文，因此非空输入的答案至少为一。
解法：区间动态规划
核心思路
[!blue]
回文的首尾字符需要相同，适合从区间两端考虑。定义
dp[i][j]为原字符串闭区间[i, j]内能选出的最长回文子序列长度。状态只限制可选择的位置范围，并不要求每次都选中两个端点。若
s[i] != s[j]，任何回文子序列都不能同时把这两个不同字符作为首尾，因此至少舍弃一端。舍弃左端后答案为dp[i + 1][j]，舍弃右端后答案为dp[i][j - 1]，取两者最大即可；两种选择可能重叠，但这里只求最大值，不影响结果。若两端相同，可以把它们放到内部最优回文的两侧，得到
dp[i + 1][j - 1] + 2。而且总能找到同时使用这两个端点的最优解：若原最优解只使用一个端点，把与它配对的同字符移到另一个外侧端点，不会减少长度；若两个端点都没使用，还可以将这对字符包在外面。因此无需再与舍弃某端的方案取最大值。单字符区间初始化为
dp[i][i] = 1。当两个相邻字符相同，内部是空区间，贡献应为零；二维表的下三角默认零，正好让dp[i + 1][i] + 2得到长度二。转移依赖下一行的
dp[i + 1][j]、dp[i + 1][j - 1]，以及本行左侧的dp[i][j - 1]。因此左端点i从右向左枚举，右端点j从左向右扩展，使用到的状态都已计算。最终整个字符串的答案为dp[0][n - 1]。
解题步骤
- 创建
n × n的整数表，默认值为零。- 从
i = n - 1倒序枚举左端点，将单字符状态dp[i][i]设为一。- 从
j = i + 1正序枚举右端点。- 两端相等时取内部答案加二；不等时取舍弃左端或右端后的较大值。
- 返回
dp[0][n - 1]。
代码实现
class Solution {
public int longestPalindromeSubseq(String s) {
int n = s.length();
int[][] dp = new int[n][n];
// 左端倒序，所需的下一行和本行左邻都已经完成。
for (int i = n - 1; i >= 0; i--) {
dp[i][i] = 1;
for (int j = i + 1; j < n; j++) {
if (s.charAt(i) == s.charAt(j)) {
// 两端相同可同时纳入，贡献两位并连接内部最优子序列。
dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return dp[0][n - 1];
}
}
func longestPalindromeSubseq(s string) int {
n := len(s)
dp := make([][]int, n)
for i := range dp {
dp[i] = make([]int, n)
}
// 左端倒序，所需的下一行和本行左邻都已经完成。
for i := n - 1; i >= 0; i-- {
dp[i][i] = 1
for j := i + 1; j < n; j++ {
if s[i] == s[j] {
// 两端相同可同时纳入，贡献两位并连接内部最优子序列。
dp[i][j] = dp[i+1][j-1] + 2
} else if dp[i+1][j] > dp[i][j-1] {
dp[i][j] = dp[i+1][j]
} else {
dp[i][j] = dp[i][j-1]
}
}
}
return dp[0][n-1]
}
复杂度分析
- 时间复杂度：$O(n^2)$，上三角中每个闭区间只计算一次，每次转移为常数时间。
- 空间复杂度：$O(n^2)$，二维表保存各区间的最优长度。
关键点总结
[!green]
- 状态表示区间内可选择的最优子序列，不能混成“整个区间是否回文”。
- 端点不同至少放弃一端；端点相同总能同时选中它们并连接内部最优解。
- 依赖决定遍历方向，单字符与空区间分别提供长度一与长度零的基础。
易错点总结
[!yellow]
- 套用回文子串的连续性判断或中心扩展，会漏掉允许跳过中间字符的子序列。
- 左端点正序遍历，会读取还没有计算的下一行状态，导致答案偏小。
- 忘记单字符初始化，会让单字符及奇数长度回文的基础长度丢失。
- 两端不相等时固定只舍弃一端，不能覆盖另一种可能更优的子序列。
- 两端相等时仍读取整个内部原串的长度，会把不能构成回文的内部字符一起计入；必须使用内部最优状态。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 5. 最长回文子串 | 中等 | 原题要求连续回文子串，本题允许跳过字符，所以按区间两端是否相等转移。 |
| 1312. 让字符串成为回文串的最少插入次数 | 困难 | 最少插入次数可由长度减最长回文子序列长度得到，两题的区间状态相互对应。 |
| 647. 回文子串 | 中等 | 用区间或中心扩展刻画回文结构；本题允许跳过字符求最长回文子序列，该题累计所有回文子串数量。 |
| 131. 分割回文串 | 中等 | 用区间或中心扩展刻画回文结构；本题允许跳过字符求最长回文子序列，该题预处理回文后枚举切分方案。 |
| 132. 分割回文串 II | 困难 | 用区间或中心扩展刻画回文结构；本题允许跳过字符求最长回文子序列，该题在回文区间上递推最少切割次数。 |