Given a string s, find the longest palindromic subsequence's length in s. You may assume that the maximum length of s is 1000.

Example 1:

Input:

"bbbab"

Output:

4

One possible longest palindromic subsequence is "bbbb".

 

Example 2:

Input:

"cbbd"

Output:

2

One possible longest palindromic subsequence is "bb".

 

Similar Questions:   

Next challenges:   

 

 方法一：迭代。

思路：dp[i][j]表示的字符串i位置到j位置之间（包括i，j）含有的palindromic subsequence的数目，那么有如果s[i]==s[j]，那么dp[i][j]=dp[i+1][j-1]+2；否则dp[i][j]=max(dp[i+1][j],dp[i][j-1])。具体实现的时候，应该先确定i和j位置之间（不包含i和j）的所有短字符串中的palindromic subsequence的数目，然后再求dp[i][j]。

 

代码：

1 public class Solution { 2     public int longestPalindromeSubseq(String s) { 3         int[][] dp = new int[s.length()][s.length()]; 4         for(int j = 0; j < s.length(); j++) { 5             dp[j][j] = 1; 6             for(int i = j - 1; i >= 0; i--) { 7                 if(s.charAt(i) == s.charAt(j)) dp[i][j] = dp[i + 1][j - 1] + 2; 8                 else dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]); 9             }10         }11         return dp[0][s.length() -1];12     }13 }

 

 

方法二：递归。

思路和方法一相同。

代码：

1 public class Solution { 2     public int longestPalindromeSubseq(String s) { 3         return helper(s, 0, s.length() - 1, new Integer[s.length()][s.length()]); 4     } 5      6     private int helper(String s, int i, int j, Integer[][] memo) { 7         if(memo[i][j] != null) return memo[i][j];//初始化Integer数组，所以数组中的每个元素是个类，如果类没有初始化就是null 8         if(i > j) return 0; 9         if(i == j) return 1;10         if(s.charAt(i) == s.charAt(j)) memo[i][j] = helper(s, i + 1, j - 1, memo) + 2;11         else memo[i][j] = Math.max(helper(s, i, j - 1, memo), helper(s, i + 1, j, memo));12         return memo[i][j];13     }14 }