描述：
給定一個字符串s未桥，找到其中最長的回文子序列〗姹福可以假設(shè)s的最大長度為1000冬耿。
示例 1:
輸入:
"bbbab"
輸出:
4
一個可能的最長回文子序列為 "bbbb"。
示例 2:
輸入:
"cbbd"
輸出:
2
一個可能的最長回文子序列為 "bb"萌壳。
思路：
遍歷每個子串亦镶，從下到上構(gòu)造dp數(shù)組，dp[i][j]
表示從i到j(luò)的最長回文子序列長度袱瓮。
狀態(tài)轉(zhuǎn)移方程：
當某子串s(i,j)中s[i]與s[j]相等時缤骨，那么其頭尾兩字符一定位于其最長回文子串中，因此該子串的最長回文子序列長度等于去掉頭尾兩字符后新子串的最長回文子序列長度加二尺借，我們可制定公式如下：dp[i][j] = dp[i + 1][j - 1] + 2绊起。當s[i]與s[j]不相等時，則dp[i][j] = max(de[i + 1][j],dp[i][j - 1]）燎斩。
class Solution {
public int longestPalindromeSubseq(String s) {
int len = s.length();
int[][] dp = new int[len][len];
for(int i=0;i<len;i++){
dp[i][i]=1;
for(int j=i-1;j>=0;j--){
if(s.charAt(i) == s.charAt(j))
dp[j][i]= dp[j+1][i-1]+2;
else
dp[j][i]=Math.max(dp[j][i-1], dp[j+1][i]);
}
}
return dp[0][len-1];
}
}
