大厂面试真题详解：最长的回文序列

给一字符串 s, 找出在 s 中的最长回文子序列的长度. 你可以假设 s 的最大长度为 1000.

在线评测地址：领扣题库官网

样例1

输入： "bbbab"
输出： 4
解释：
一个可能的最长回文序列为 "bbbb"

样例2

输入： "bbbbb"
输出： 5

算法：DP

设dpi表示在s[i...j]中最长回文序列的长度。
对于初始化区间长度

• 长度为0时，dpi = 1

• 对于 dpi，假设s[i] != s[j]

  • 那么在sub(i,j)的最大回文串中,s[i]与s[j]不会同时出现，那么sub(i,j)的最大回文串要么出现在sub(i+1,j),要么出现在sub(i,j-1)，因此我们的状态转移方程就得到了dpi = max(dpi+1, dpi)

• 假设s[i]==s[j]

  • 那么直接认为这俩个匹配，会同时出现在结果中，然后加上sub(i+1,j-1)的最大回文串，即dpi = dpi+1 + 2
• 最后的结果就在dp0

复杂度分析

• 时间复杂度O(len(s)*len(s))

  • 嵌套循环，顺着i减小的方向，以j增大的方向遍历

• 空间复杂度O(len(s)*len(s))

  • 二维dp的大小

public class Solution {
    /**
     * @param s: the maximum length of s is 1000
     * @return: the longest palindromic subsequence's length
     */
    public int longestPalindromeSubseq(String s) {
        int size = s.length();
        char[] ss = s.toCharArray();
        if (size <= 1){
            return size;
        }
        int[][] dp = new int[size][size];
        //初始化        
        for (int i = 0; i < size; ++i) {
            dp[i][i] = 1;
        }
        for (int i = size - 1; i >= 0; --i) {
            for (int j = i + 1; j < size; ++j) {
                if (ss[i] == ss[j]) {//s[i]==s[j]时的转移方程
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } 
                else {//s[i]！=s[j]时的转移方程
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
                }
            }
        }
        //最后结果在dp[0][size - 1]中
        return dp[0][size - 1];
    }
}

更多题解参考：九章官网solution