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".

* 子序列不一定连续,双指针，写出状态方程就好写了，二维数组res[sta][end]代表回文的开头和结尾坐标分别是sta和end的长度*/

public int longestPalindromeSubseq(String s) {
int len = s.length();
int[][] res = new int[len][len];
return len(0,len-1,res,s);
}
public int len(int sta,int end,int[][] res,String s)
{
　　　　//由于max函数中要求两个长度，两次求值过程中为了避免重复工作，可以直接利用res中已经存在的值，可以提高很多效率
if (res[sta][end] != 0)
return res[sta][end];
if (sta > end)
return 0;
if (sta == end)
return 1;
//状态方程：
//if[s(sta) == s(end)]:d[sta][end] = d[sta+1][end-1] + 2;
//else[s(sta) != s(end)]:d[sta][end] = max[d[sta+1][end],d[sta][end-1]]
if (s.charAt(sta) == s.charAt(end))
{
res[sta][end] = len(sta+1,end-1,res,s) + 2;
}
else
{
res[sta][end] = Math.max(len(sta+1,end,res,s),len(sta,end-1,res,s));
}
return res[sta][end];
}