題意理解：

????????給你一個(gè)字符串?s?，找出其中最長(zhǎng)的回文子序列，并返回該序列的長(zhǎng)度。

????????子序列定義為：不改變剩余字符順序的情況下，刪除某些字符或者不刪除任何字符形成的一個(gè)序列。

? ? ? ? 回文理解為元素對(duì)稱的字串，這里求字符串中最長(zhǎng)的對(duì)稱字串的長(zhǎng)度。

? ? ? ? 使用動(dòng)態(tài)規(guī)劃的思路來進(jìn)行解題。

解題思路：

? ? ? ? （1）定義dp數(shù)組

? ? ? ? ? ? ? ? dp[i][j]表示從i到j(luò)的字串中最長(zhǎng)回文序列的長(zhǎng)度

? ? ? ? （2）遞推公式

? ? ? ? ? ? ? ? 當(dāng)且僅當(dāng)s[i]==s[j]

????????? ? ? ? dp[i][j]=dp[i+1][j-1]+2

? ? ? ? ? ? ? ? 否則：dp[i][j]=Max(dp[i+1][j],dp[i][j-1],dp[i+1][j-1])

? ? ? ? ? (3)? 初始化：一個(gè)元素是回文，所以dp[i][j],i==j時(shí)，值為1

? ? ? ? ? (4）由于dp[i][j]受dp[i+1][j-1]影響，所以，遍歷順序從左到右，從上到下

? ? ? ? ? ?最后返回dp[0][s.size-1]

1.動(dòng)態(tài)規(guī)劃解題

 public int longestPalindromeSubseq(String s) {int[][] dp=new int[s.length()][s.length()];for(int i=0;i<s.length();i++){Arrays.fill(dp[i],0);dp[i][i]=1;}for(int i=s.length()-1;i>=0;i--){for(int j=i+1;j<s.length();j++){if(s.charAt(i)==s.charAt(j)){dp[i][j]=dp[i+1][j-1]+2;}else{dp[i][j]=Math.max(Math.max(dp[i][j-1],dp[i+1][j]),dp[i+1][j-1]);}}}return dp[0][s.length()-1];}

2.復(fù)雜度分析

時(shí)間復(fù)雜度：O(n^2)

空間復(fù)雜度：O(n^2)