DP----leetcode516最长回文子序列

这个题也非常有意思：
给定一个字符串s，找到其中最长的回文子序列。可以假设s的最大长度为1000。

示例 1:
输入:

“bbbab”
输出:

4
一个可能的最长回文子序列为 “bbbb”。

示例 2:
输入:

“cbbd”
输出:

2
一个可能的最长回文子序列为 “bb”。

    public static int longestPalindromeSubseq(String s) {
       if(s.equals(""))
    	   return 0;
       int i,j,len=s.length(),dp[][]=new int[len][len],ans=1,k;
       char ch[]=s.toCharArray();
       for(i=0;i<len;i++)
    	   for(j=i;j<len;j++)
    		   dp[i][j]=1;
       for(i=0;i<len-1;i++) {
    	   if(ch[i]==ch[i+1]) {
    		   ans=2;
    		   dp[i][i+1]=2;
    	   }
       }
       for(k=2;k<len;k++) {
    	   for(i=0;i<len-k;i++) {
    		   j=i+k;
    		   if(ch[i]==ch[j]) {
    			   dp[i][j]=dp[i+1][j-1]+2;
    			   ans=Math.max(ans, dp[i][j]);
    		   }
    		   else{
    			   dp[i][j]=Math.max(dp[i+1][j], dp[i][j-1]);
    		   }
    	   }
       }
       return ans;
    }

总体来说就是动态规划，dp[i][j]表示从i到j的最长回文子序列
当ch[i]==ch[j]，dp[i][j]=dp[i+1][j-1]+2,否则dp[i][j]=max(dp[i+1][j],dp[i][j-1])