最长回文子序列 图解题解

可跳字符的回文子序列，怎么算最长

给一个字符串 s，挑出一个正着读、倒着读都一样的子序列，要它尽可能长，返回长度。子序列可跳字符、但相对顺序不变，比如 bbbab 挑出 bbbb（跳过中间的 a）是长度 4 的回文。这题最容易和最长回文子串（LeetCode 5）弄混：子串要连续，子序列可跳着挑。

为什么不能把所有子序列列出来数

最直接是把所有子序列列出来逐个查，留最长的回文。可长度 n 的串有 2^n 个子序列，n 稍大就数不完（大 O 记号描述规模变大时操作数怎么涨，这里 O(2^n)）。它们大量重叠、同一小段被反复重验，把每段答案存下来只算一次就是动态规划（算过的子问题记下别重算）。

为什么状态要盯一个区间 dp[i][j]

回文判断天然从两头往中间收，状态就盯一个区间。定义 dp[i][j] 为子串 s[i..j] 的最长回文子序列长度，i 左端、j 右端，答案是 dp[0][n-1]。最短区间是单字符 dp[i][i]=1（一个字母自己就是回文），是长区间的基石；空区间（i 大于 j）记 0。

两端相等为什么 +2、不等为什么丢一端取大

算 dp[i][j] 只看两端 s[i] 和 s[j]。相等时它俩能当回文的最外层，把里面 s[i+1..j-1] 的最长回文包起来、两头各加一个，dp[i][j]=dp[i+1][j-1]+2。不等时它俩没法同时当两头，只能丢一个——丢左端剩 dp[i+1][j]，丢右端剩 dp[i][j-1]，取大：dp[i][j]=max(dp[i+1][j], dp[i][j-1])。

填表方向有坑：用到的 dp[i+1][j-1]、dp[i+1][j]、dp[i][j-1] 都比区间 [i,j] 更短。不能按行列顺序填，得按区间长度从短到长填——短的先算好、长的才有值可用。等价写法是外层 i 从大到小、内层 j 从小到大。

拿 bbbab 把这张表一格格填出来

下标 0 到 4 是 b、b、b、a、b。先铺对角线（表里从左上到右下、行号等于列号那条线），五个单字符 dp[i][i]=1。长度 2：dp[0][1] 相等，内部空记 0、+2 得 2；dp[1][2] 同理得 2；dp[2][3] 不等取 max(1,1)=1；dp[3][4] 不等取 1。

长度 3：dp[0][2] 相等得 dp[1][1]+2=3；dp[1][3] 不等取 max(dp[2][3]=1, dp[1][2]=2)=2；dp[2][4] 相等得 3。长度 4：dp[0][3] 不等取 max(2, 3)=3；dp[1][4] 相等得 dp[2][3]+2=3。长度 5：dp[0][4] 相等得 dp[1][3]+2=4，右上角就是答案 bbbb。

填表顺序填反、长度 2 漏 +2 会怎样

上三角约 n²/2 个格子、每格一次比较，时间 O(n²)；存整张二维表，空间 O(n²)，压成一维滚动数组（只留最近一行、循环覆盖旧值）可降到 O(n)。两个边界别弄错：填表顺序按行列填会读到还没算的长区间，必须按区间长度递增；长度 2 的区间相等时内部空记 0、+2 得 2，别漏这个 +2。

Python

def longestPalindromeSubseq(s):
    n = len(s)
    dp = [[0]*n for _ in range(n)]
    for i in range(n): dp[i][i] = 1
    for L in range(2, n+1):
        for i in range(0, n-L+1):
            j = i + L - 1
            if s[i] == s[j]:
                dp[i][j] = (dp[i+1][j-1] if i+1<=j-1 else 0) + 2
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
    return dp[0][n-1]

C++

int longestPalindromeSubseq(string s){
    int n = s.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for(int i = 0; i < n; i++) dp[i][i] = 1;
    for(int L = 2; L <= n; L++)
        for(int i = 0; i + L - 1 < n; i++){
            int j = i + L - 1;
            if(s[i] == s[j]) dp[i][j] = (i+1<=j-1 ? dp[i+1][j-1] : 0) + 2;
            else dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
        }
    return dp[0][n-1];
}

Java

int longestPalindromeSubseq(String s){
    int n = s.length();
    int[][] dp = new int[n][n];
    for (int i = 0; i < n; i++) dp[i][i] = 1;
    for (int L = 2; L <= n; L++)
        for (int i = 0; i + L - 1 < n; i++) {
            int j = i + L - 1;
            if (s.charAt(i) == s.charAt(j))
                dp[i][j] = (i+1<=j-1 ? dp[i+1][j-1] : 0) + 2;
            else dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
        }
    return dp[0][n-1];