516. 最长回文子序列
题目描述
输入字符串 s。
子序列是从 s 中删掉若干字符（也可以一个不删）后，其余字符保持原顺序得到的串，不要求在原串中相邻。
在所有正读反读都一样的子序列中，返回最长者的长度。
示例 1
输入：s = "bbbab" 输出：4
解释：取出四个 'b' 得到 "bbbb"，长度为 4。
示例 2
输入：s = "cbbd" 输出：2
解释："bb" 是最长的回文子序列。
数据范围
1 <= s.length <= 1000s只含小写英文字母。
解题思路：区间动态规划
区间 DP。dp[i][j] 表示 s[i..j] 中最长回文子序列的长度。如果两端 s[i] == s[j]，它们可以同时包在内部最优解外面：dp[i+1][j-1] + 2。否则两端至少有一个不用，取 max(dp[i+1][j], dp[i][j-1])。i 从大到小、j 从小到大遍历，确保用到的更短区间都已算好。
为什么正确
处理第 i 行时，第 i+1 行已经全部算好；同一行左侧的 dp[i][j-1] 也已算好。
复杂度分析
时间 O(n^2)，空间 O(n^2)（可压到 O(n)）。
易错点
当 j = i + 1 且两端相等时，dp[i+1][j-1] 指向空区间（左下角的 0），结果正好是 2。循环顺序写反（i 从小到大）会读到尚未计算的格子。另外不要和“最长回文子串”混淆，子序列不要求连续。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
dp[i][i] = 1
for j in range(i + 1, n):
if s[i] == s[j]:
dp[i][j] = dp[i + 1][j - 1] + 2
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
return 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];
}
}class Solution {
public:
int longestPalindromeSubseq(string s) {
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int i = n - 1; i >= 0; i--) {
dp[i][i] = 1;
for (int j = i + 1; j < n; j++) {
if (s[i] == s[j]) {
dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
dp[i][j] = 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 {
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
}
}
}
return dp[0][n-1]
}var longestPalindromeSubseq = function(s) {
const n = s.length;
const dp = Array.from({ length: n }, () => new Array(n).fill(0));
for (let i = n - 1; i >= 0; i--) {
dp[i][i] = 1;
for (let j = i + 1; j < n; j++) {
if (s[i] === s[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];
};function longestPalindromeSubseq(s: string): number {
const n = s.length;
const dp = Array.from({ length: n }, () => new Array(n).fill(0));
for (let i = n - 1; i >= 0; i--) {
dp[i][i] = 1;
for (let j = i + 1; j < n; j++) {
if (s[i] === s[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];
}其他解法
区间 DP 直接以子串两端为状态，根据两端字符是否相等转移；LCS 归约把问题转化为 s 与其反转串的公共子序列，复杂度相同，体现了问题转化的思路。
解法 2：转化为最长公共子序列 时间 O(n²)，空间 O(n)
回文子序列正着读和反着读一样，所以它既是 s 的子序列，也是 s 反转串 t 的子序列。反过来，s 与 t 的最长公共子序列长度恰好等于最长回文子序列长度。于是直接套用 LCS 的二维 DP，并用滚动数组把空间降到一维。
复用经典的 LCS 模板，把新问题归约到已知问题。需要额外说明为什么 LCS 长度等于答案；空间优化后也无法直接还原具体的回文序列。
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
# 最长回文子序列 = s 与其反转串的最长公共子序列
t = s[::-1]
n = len(s)
prev = [0] * (n + 1)
for i in range(1, n + 1):
cur = [0] * (n + 1)
for j in range(1, n + 1):
if s[i - 1] == t[j - 1]:
cur[j] = prev[j - 1] + 1
else:
cur[j] = max(prev[j], cur[j - 1])
prev = cur
return prev[n]class Solution {
public int longestPalindromeSubseq(String s) {
String t = new StringBuilder(s).reverse().toString();
int n = s.length();
int[] prev = new int[n + 1], cur = new int[n + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (s.charAt(i - 1) == t.charAt(j - 1)) cur[j] = prev[j - 1] + 1;
else cur[j] = Math.max(prev[j], cur[j - 1]);
}
int[] tmp = prev;
prev = cur;
cur = tmp;
}
return prev[n];
}
}class Solution {
public:
int longestPalindromeSubseq(string s) {
string t(s.rbegin(), s.rend());
int n = s.size();
vector<int> prev(n + 1, 0), cur(n + 1, 0);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (s[i - 1] == t[j - 1]) cur[j] = prev[j - 1] + 1;
else cur[j] = max(prev[j], cur[j - 1]);
}
swap(prev, cur);
}
return prev[n];
}
};func longestPalindromeSubseq(s string) int {
n := len(s)
prev, cur := make([]int, n+1), make([]int, n+1)
for i := 1; i <= n; i++ {
for j := 1; j <= n; j++ {
// t[j-1] = s[n-j]，t 为 s 的反转
if s[i-1] == s[n-j] {
cur[j] = prev[j-1] + 1
} else if prev[j] > cur[j-1] {
cur[j] = prev[j]
} else {
cur[j] = cur[j-1]
}
}
prev, cur = cur, prev
}
return prev[n]
}var longestPalindromeSubseq = function(s) {
const t = s.split('').reverse().join('');
const n = s.length;
let prev = new Array(n + 1).fill(0), cur = new Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= n; j++) {
if (s[i - 1] === t[j - 1]) cur[j] = prev[j - 1] + 1;
else cur[j] = Math.max(prev[j], cur[j - 1]);
}
[prev, cur] = [cur, prev];
}
return prev[n];
};function longestPalindromeSubseq(s: string): number {
const t = s.split('').reverse().join('');
const n = s.length;
let prev = new Array(n + 1).fill(0), cur = new Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= n; j++) {
if (s[i - 1] === t[j - 1]) cur[j] = prev[j - 1] + 1;
else cur[j] = Math.max(prev[j], cur[j - 1]);
}
[prev, cur] = [cur, prev];
}
return prev[n];
}