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

点此在线做题

样例 1

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

样例 2

输入： "bbbbb" 输出：5 

算法：DP

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

• 长度为 0 时，dp[i][i] = 1
• 对于 dp[i][j]，假设 s[i] != s[j]
  • 那么在 sub(i,j)的最大回文串中,s[i]与 s[j]不会同时出现，那么 sub(i,j)的最大回文串要么出现在 sub(i+1,j),要么出现在 sub(i,j-1)，因此我们的状态转移方程就得到了 dp[i][j] = max(dp[i+1][j], dp[i][j-1])
• 假设 s[i]==s[j]
  • 那么直接认为这俩个匹配，会同时出现在结果中，然后加上 sub(i+1,j-1)的最大回文串，即 dp[i][j] = dp[i+1][j-1] + 2
• 最后的结果就在 dp[0][len_s-1]

复杂度分析

• 时间复杂度 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];     } } 

更多题解参考