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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string 一个字符串由小写字母构成，长度小于5000
     * @return int
     */
    public int longestPalindromeSubSeq (String s) {
        // write code here
        if(s.length()==1) return 1;
        char[] s1 = s.toCharArray();
        char[] s2 = new char[s1.length];
        int[][] dp = new int[s1.length][s1.length];
        dp[0][0] = (s1[0]==s1[s1.length-1]?1:0);
        char tmp = 0;
        for(int i=0;i<s1.length;i++){
            s2[i] = s1[s1.length-1-i];
        }
        for(int i=1;i<s2.length;i++){
            if(s1[0]==s2[i]) dp[0][i] = 1;
            dp[0][i] = Math.max(dp[0][i],dp[0][i-1]);
        }
        for(int i=1;i<s1.length;i++){
            if(s1[i]==s2[0]) dp[i][0] = 1;
            dp[i][0] = Math.max(dp[i][0],dp[i-1][0]);
        }
        for(int i=1;i<s1.length;i++){
            for(int j=1;j<s2.length;j++){
                if(s1[i]==s2[j]) dp[i][j] = dp[i-1][j-1]+1;
                dp[i][j] = Math.max(dp[i][j],dp[i][j-1]);
                dp[i][j] = Math.max(dp[i][j],dp[i-1][j]);
            }
        }
        return dp[s1.length-1][s2.length-1];
    }
}