LeetCode 516. 最长回文子序列 · Java 实现
题意
给定字符串 s，求其最长回文子序列的长度。
注意区分"子序列"和"子串"：
· 子序列不要求连续，可以跳跃（如 bbbab 的最长回文子序列是 bbbb，长度 4）
· 子串必须连续（那是另一道题 647/5）
示例：
s = "bbbab" → 4 (bbbb) s = "cbbd" → 2 (bb)思路一：区间 DP（标准解法，推荐）
状态定义：
dp[i][j] = 区间 s[i…j] 内的最长回文子序列长度
转移方程：
情况 转移
s[i] == s[j] 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])
初始化： dp[i][i] = 1（单个字符本身就是长度 1 的回文）
遍历顺序的关键：dp[i][j] 依赖 dp[i+1][j-1]、dp[i+1][j]、dp[i][j-1]，即依赖更长区间（i 更大、j 更小）。
所以必须：i 从 n-1 倒序，j 从 i+1 正序。
classSolution{publicintlongestPalindromeSubseq(Strings){intn=s.length();int[][]dp=newint[n][n];// 单字符天然是长度 1 的回文for(inti=0;i<n;i++)dp[i][i]=1;for(inti=n-1;i>=0;i--){for(intj=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]);}}}returnn==0?0:dp[0][n-1];}}复杂度： 时间 O(n²)，空间 O(n²)
思路二：滚动数组空间优化（一维 DP）
观察转移：dp[i][j] 只依赖下一行 dp[i+1][*] 和本行左侧 dp[i][j-1]，可以用一维数组 + 一个变量保存"上一轮的值"来压缩。
classSolution{publicintlongestPalindromeSubseq(Strings){intn=s.length();if(n==0)return0;int[]dp=newint[n];java.util.Arrays.fill(dp,1);// dp[j] 初始表示 dp[j][j] = 1for(inti=n-1;i>=0;i--){intpre=0;// 表示 dp[i+1][j-1]，当 j = i+1 时为 dp[i+1][i] = 0for(intj=i+1;j<n;j++){inttemp=dp[j];// 暂存 dp[i+1][j]if(s.charAt(i)==s.charAt(j)){dp[j]=pre+2;// dp[i+1][j-1] + 2}else{dp[j]=Math.max(dp[j],dp[j-1]);// dp[j] = dp[i+1][j]（尚未更新）// dp[j - 1] = dp[i][j-1]（本轮已更新）}pre=temp;// 为下一个 j 准备 dp[i+1][j-1]}}returndp[n-1];}}复杂度： 时间 O(n²)，空间 O(n)
⚠️ pre 的更新时机是易错点：必须先 temp = dp[j] 把"旧值"（即 dp[i+1][j]）存下来，等 dp[j] 用完后，再把 pre = temp 供下一列 j+1 用作 dp[i+1][(j+1)-1] = dp[i+1][j]。顺序反了就错。
思路三：转化为 LCS
一个回文串的"前一半"必然等于"后一半的反转"，所以：
s 的最长回文子序列 = s 与 reverse(s) 的最长公共子序列（LCS）长度。
classSolution{publicintlongestPalindromeSubseq(Strings){Stringt=newStringBuilder(s).reverse().toString();intn=s.length();int[]dp=newint[n+1];for(inti=1;i<=n;i++){intpre=0;for(intj=1;j<=n;j++){inttemp=dp[j];if(s.charAt(i-1)==t.charAt(j-1)){dp[j]=pre+1;}else{dp[j]=Math.max(dp[j],dp[j-1]);}pre=temp;}}returndp[n];}}· 思路直观，但常数略大（多构造一个 reverse 串）。
· 面试中作为"第二种角度"可以提，主推思路一。
三种方法对比
方法 时间 空间 推荐度
区间 DP（二维） O(n²) O(n²) ⭐⭐⭐⭐⭐ 面试首选，逻辑最清晰
区间 DP（一维滚动） O(n²) O(n) ⭐⭐⭐⭐ 空间优化加分
转 LCS O(n²) O(n) ⭐⭐⭐ 思路巧妙但略绕
关键坑点 ⚠️
- 子序列 vs 子串混淆
· 本题是子序列（可跳），别写成中心扩展或区间子串判定。
· 典型反例：“bbbab” 的结果是 4（bbbb），若是子串答案会不同。 - 遍历顺序写反
· dp[i][j] 依赖 dp[i+1][*] 和 dp[i][j-1]，所以 i 必须倒序、j 必须正序。
· 如果 i 正序，dp[i+1][…] 还没算出来，全是 0。 - s[i] == s[j] 时要加 2，不是 1
· 首尾两字符都加进来。 - j 从 i+1 开始，不是 i
· dp[i][i] = 1 已经初始化，j == i 不应该进循环（否则会把 dp[i][i] 覆盖）。 - i+1 > j-1 的边界
· 当 j == i+1 时，dp[i+1][j-1] = dp[i+1][i]，长度为 0 的区间。二维数组里它是 0（未初始化），正好正确；一维滚动版里要用 pre = 0 来模拟。
· 如果初始化为 1 会导致 “aa” 这种输入被算成 3。 - 空串和单字符
· n == 0 返回 0；n == 1 返回 1（因为 dp[0][0] 已初始化为 1，且内层循环不执行，直接返回 dp[0][0] = 1）。 - 空间优化时 pre 更新时机
· 见思路二代码注释：先用旧值，再更新 pre。顺序反了会把"本行刚算出的值"误当"上一行的值"。
一句话总结
区间 DP：dp[i][j] 表示 s[i…j] 的最长回文子序列长度。首尾相等 +2，不等取 max，i 倒序 j 正序遍历。O(n²) 时间，O(n) 空间可用滚动数组优化。
