給你一個(gè)字符串?s?娇斩，找出其中最長(zhǎng)的回文子序列，并返回該序列的長(zhǎng)度悠就。
子序列定義為：不改變剩余字符順序的情況下敦第，刪除某些字符或者不刪除任何字符形成的一個(gè)序列
示例 1：
????????????輸入：s = "bbbab"
????????????輸出：4
????????????解釋：一個(gè)可能的最長(zhǎng)回文子序列為 "bbbb" 。
示例 2：
????????????輸入：s = "cbbd"
????????????輸出：2
????????????解釋：一個(gè)可能的最長(zhǎng)回文子序列為 "bb" 回怜。
解題思路：可使用動(dòng)態(tài)規(guī)劃進(jìn)行求解大年，dp[i][j]? 表示為 s[i到j(luò)]? 的最長(zhǎng)的回文子序列長(zhǎng)度.
? ? ? ? ? ? ? ? ? ?if(s[i] == s[j])换薄，那么 dp[i][j] = dp[i+1][j-1] + 2；
? ? ? ? ? ? ? ? ? ?if(s[i] != s[j])翔试， 那么 dp[i][j] = MAX(dp[i][j-1]轻要，dp[i+1][j])。
? ? ? ? ? ? ? ? ? ?最終字符串?s的最長(zhǎng)回文子序列長(zhǎng)度為 dp[0][s.length-1]垦缅。
public?int?longestPalindromeSubseq(String?s)?{
????????int?l?=?s.length();
????????int[][]?dp?=?new?int[l][l];??
????????for(int?i=0;?i<l;?i++)?{
????????????dp[i][i]?=?1;? //初始化dp數(shù)組
????????}
????????for(int?i=l-1;?i>=0;?i--)?{? //?i遞減所以總能知道dp[i+1][j]的值
????????????for(int?j=i+1;?j<l;?j++)?{? //j遞增所以總能知道dp[i][j-1]的值
????????????????if(s.charAt(i)?==?s.charAt(j))?{
????????????????????dp[i][j]?=?dp[i+1][j-1]?+?2;
????????????????}?else?{
????????????????????dp[i][j]?=?Math.max(dp[i][j-1],?dp[i+1][j]);
????????????????}
????????????}
????????}
????????return?dp[0][l-1];
????}
