跳至主要內容

最长回文子序列——区间DP的正确遍历顺序

老张2026/4/30大约 9 分钟

最长回文子序列——区间DP的正确遍历顺序

适读人群：Java后端工程师、区间DP学习者 | 阅读时长：约20分钟 | 难度：Medium

开篇故事

区间DP是我认为DP里最容易"反直觉"的一类。

大多数DP是线性推进的：从左往右，从小到大，每个状态只依赖之前的状态。逻辑很顺。但区间DP不一样，它处理的是"一段区间"，大区间依赖小区间，遍历顺序如果写错，计算大区间时小区间还没算出来，直接就出错了。

我第一次写最长回文子序列，习惯性地写成 for (int i = 0; i < n; i++) for (int j = i; j < n; j++)，自以为是"从小到大"。但仔细一想，当计算 dp[0][4] 时需要用到 dp[1][3]，而按照我的遍历顺序，当 i=0 时，dp[1][3] 还没有被计算过（j 只是在变大，i=1 时才会计算 dp[1][j]）。结果就是读了一个未初始化的值。

区间DP的正确遍历顺序是"按区间长度从小到大"：先算所有长度为1的区间，再算长度为2的，以此类推。这一点搞清楚了，区间DP就入门了。

一、题目解析

题号：LeetCode 516. Longest Palindromic Subsequence

题目描述：给你一个字符串 s，找出其中最长的回文子序列，并返回该序列的长度。子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例：

  • 输入：s = "bbbab"，输出：4（"bbbb"）
  • 输入：s = "cbbd"，输出：2（"bb"）

数据范围：1 ≤ s.length ≤ 1000

核心考点：区间DP，正确遍历顺序，转化为LCS的方法

二、DP思路推导

2.1 区间DP的核心思想

区间DP的核心：用更短的区间的结果推出更长的区间的结果。

对于字符串 s 的某个区间 [i, j]：

  • 考察两端字符 s[i] 和 s[j] 的关系
  • 由此决定如何从 [i+1, j] 或 [i, j-1] 或 [i+1, j-1] 推导出 [i, j] 的结果

2.2 状态定义

定义 dp[i][j] = 字符串 s[i..j] 的最长回文子序列长度

2.3 状态转移方程推导

关注区间 [i, j] 两端的字符 s[i] 和 s[j]：

情况一：s[i] == s[j]

两端字符相等！可以同时加入回文子序列，长度 +2：

dp[i][j] = dp[i+1][j-1] + 2

特别地，当 i == j 时，单个字符本身就是回文，dp[i][i] = 1；当 i+1 == j 且 s[i] == s[j] 时，dp[i][j] = 2，dp[i+1][j-1] = dp[j][j-1]（空区间），需要处理为0。

情况二：s[i] != s[j]

两端字符不等，不能同时加入回文子序列。分别考虑包含左端、包含右端的情况，取最大：

dp[i][j] = max(dp[i+1][j], dp[i][j-1])

完整状态转移方程：

dp[i][j] = dp[i+1][j-1] + 2            if s[i] == s[j]
dp[i][j] = max(dp[i+1][j], dp[i][j-1]) if s[i] != s[j]

2.4 为什么遍历顺序至关重要

计算 dp[i][j] 需要：

  • dp[i+1][j-1]：比 [i,j] 小2的区间（长度少2）
  • dp[i+1][j]：比 [i,j] 小1的区间（i+1开始）
  • dp[i][j-1]：比 [i,j] 小1的区间（j-1结束）

所以计算 [i,j] 之前，所有更短的区间都必须已经计算完。

正确遍历顺序：按区间长度从小到大

for (int len = 1; len <= n; len++) {       // 枚举区间长度
    for (int i = 0; i + len - 1 < n; i++) { // 枚举区间左端点
        int j = i + len - 1;                // 右端点
        // 计算 dp[i][j]
    }
}

错误遍历顺序示例：

// 错误！按i从小到大，j从小到大遍历
for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
        // 计算dp[i][j]时，dp[i+1][j-1]可能还未计算
    }
}

2.5 状态转移示意

s = "bbbab"（n=5）

初始化：dp[i][i] = 1（单个字符）

| len=1 | len=2 | len=3 | len=4 | len=5 |
|  i==j | 相邻两字符 | 三字符区间 | 四字符区间 | 全串 |

len=1: dp[0][0]=1, dp[1][1]=1, dp[2][2]=1, dp[3][3]=1, dp[4][4]=1
len=2: 
  [0,1]='bb': s[0]==s[1], dp[0][1]=dp[1][0]+2=2（空区间为0）
  [1,2]='bb': dp[1][2]=2
  [2,3]='ba': dp[2][3]=max(dp[3][3], dp[2][2])=1
  [3,4]='ab': dp[3][4]=max(dp[4][4], dp[3][3])=1
len=3:
  [0,2]='bbb': s[0]==s[2], dp[0][2]=dp[1][1]+2=3
  [1,3]='bba': s[1]!=s[3], dp[1][3]=max(dp[2][3], dp[1][2])=max(1,2)=2... 
len=4:
  [0,3]='bbba': dp[0][3]=max(dp[1][3],dp[0][2])=max(2,3)=3... （s[0]!=s[3]）
len=5:
  [0,4]='bbbab': s[0]=='b'==s[4]=='b', dp[0][4]=dp[1][3]+2=4 ✓

三、解法一：标准区间DP

public class LongestPalindromicSubsequence {
    
    /**
     * 516. 最长回文子序列 - 区间DP
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(n^2)
     */
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        
        // dp[i][j] = s[i..j]的最长回文子序列长度
        int[][] dp = new int[n][n];
        
        // 边界：单个字符，长度为1
        for (int i = 0; i < n; i++) dp[i][i] = 1;
        
        // 按区间长度从小到大枚举（关键！）
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                
                if (s.charAt(i) == s.charAt(j)) {
                    // 两端字符相等：扩展内部区间+2
                    // 注意：当len==2时，dp[i+1][j-1]=dp[i+1][i]（空区间），值为0
                    dp[i][j] = (len == 2 ? 0 : 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];
    }
}

Mermaid遍历顺序示意：

四、解法二：转化为LCS（另一种思路）

洞察：s 的最长回文子序列 = s 和 reverse(s) 的最长公共子序列！

原因：回文子序列正着读和倒着读相同，所以它必然同时是 s 和 reverse(s) 的子序列，是两者的LCS。

/**
 * 516. 最长回文子序列 - 转化为LCS
 * 时间复杂度：O(n^2)
 * 空间复杂度：O(n^2)
 */
public int longestPalindromeSubseqLCS(String s) {
    String t = new StringBuilder(s).reverse().toString();
    int n = s.length();
    int[][] dp = new int[n + 1][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)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    
    return dp[n][n];
}

两种解法复杂度相同，但LCS解法更简洁，面试时可以作为一种优雅的备选展示思路。

五、解法三：空间优化

区间DP不像线性DP那么容易做空间压缩，因为依赖关系更复杂（需要左下方向的 dp[i+1][j-1]）。

一种做法是用两行滚动数组，但需要注意 dp[i+1][j-1] 的保存问题。

/**
 * 516. 最长回文子序列 - 空间压缩到O(n)
 * 技巧：外层i从大到小，内层j从小到大，用一维数组+prev保存
 */
public int longestPalindromeSubseqOptimized(String s) {
    int n = s.length();
    int[] dp = new int[n];
    
    // 初始化：每个位置单字符LCS=1
    Arrays.fill(dp, 1);
    
    // 外层i从后向前（因为dp[i]依赖dp[i+1]..）
    for (int i = n - 2; i >= 0; i--) {
        int prev = 0;  // 代表dp[i+1][j-1]（j从i+1开始前的初始值）
        for (int j = i + 1; j < n; j++) {
            int temp = dp[j];  // 保存dp[i+1][j]
            if (s.charAt(i) == s.charAt(j)) {
                dp[j] = prev + 2;
            } else {
                dp[j] = Math.max(dp[j], dp[j - 1]);
            }
            prev = temp;  // 下一次迭代的dp[i+1][j-1]就是本次的dp[i+1][j]
        }
    }
    
    return dp[n - 1];
}

六、举一反三

区间DP同类题目：

  1. LeetCode 647. 回文子串：计数所有回文子串，dp[i][j] 是布尔型
  2. LeetCode 1000. 合并石头的最低成本：经典区间DP，按长度枚举
  3. LeetCode 312. 戳气球：逆向区间DP（下一篇详讲）
  4. LeetCode 375. 猜数字大小II：区间DP求最坏情况最优策略

区间DP通用模板：

// 区间DP通用框架
int[][] dp = new int[n][n];
// 初始化长度为1的区间
for (int i = 0; i < n; i++) dp[i][i] = 初始值;

// 按区间长度从小到大
for (int len = 2; len <= n; len++) {
    for (int i = 0; i + len - 1 < n; i++) {
        int j = i + len - 1;
        // 状态转移
        dp[i][j] = f(dp[i+1][j], dp[i][j-1], dp[i+1][j-1], ...);
    }
}
return dp[0][n-1];

七、踩坑实录

坑一：遍历顺序写错（最高频失误）

用直觉的 i从0到n, j从i到n 遍历，会导致计算大区间时小区间还未就绪。必须按区间长度从小到大遍历，这是区间DP的铁律。

坑二：len=2时访问dp[i+1][j-1]=dp[i+1][i]

当 len=2 时，j=i+1，dp[i+1][j-1]=dp[i+1][i]，这是一个空区间（左端大于右端），应当视为0。Java中int数组默认0，所以如果你一开始没有初始化dp[i+1][i]为0（事实上也不应该初始化负长度区间），就需要在代码里特判 len==2 的情况，直接赋值2（如果两端字符相等）或1（如果不等，单字符回文）。

坑三：混淆子序列和子串

本题求的是子序列（可以不连续），不是子串（必须连续）。如果用解子串（如连续回文子串）的思路来做，会少考虑很多情况。LeetCode 5（最长回文子串）和516（最长回文子序列）是两道完全不同的题，不要混淆。

坑四：转化LCS时字符串索引混乱

LCS解法中，s对应的下标是 i-1，reverse(s)的下标是 j-1（1-indexed），容易和0-indexed混淆。建议和LCS代码保持一致，统一用1-indexed。

八、总结

最长回文子序列是区间DP的入门经典题。核心知识点：

  1. 区间DP遍历顺序：必须按区间长度从小到大，而非按端点的字典序
  2. 状态转移：两端字符相等时取内部+2，不等时取两种缩短后的最大值
  3. 等价转化：可以转化为 s 和 reverse(s) 的LCS，代码更简洁
解法时间空间
区间DPO(n²)O(n²)
LCS转化O(n²)O(n²)
空间压缩O(n²)O(n)
编辑此页
最近更新:
贡献者: xiaozhangge