题解 | #最长回文子序列#

这个题可以参考最长公共子序列。最长回文子序列可以通过构造两个相反的字符串求最长子序列的方式求出。采用动态规划，时间复杂度O(n^2)空间复杂度O（n^2)。进一步的，还能求出这个最长的子序列具体的结果。

public class Solution {
    public int longestPalindromeSubSeq (String s) {
        // write code here
        int dp[][] = new int[s.length()+1][s.length()+1];
        String s1 = new StringBuilder(s).reverse().toString();
        for(int i=1;i<=s.length();++i){
            for(int j=1;j<=s.length();++j){
                if(s.charAt(i-1)==s1.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[s.length()][s.length()];
    }
}